POJ 2398 Toy Storage(计算几何)

题目

描述略,此题和 POJ 2318 基本是类似的,只不过最后统计的是每个分区内的玩具个数有几个,还有坑点就是题目输入的数据不像 POJ 2318 的数据是按照点的坐标和线段端点点的坐标从左到右依次输入,而是乱输入的,因此需要建立结构体将其排序。给出 POJ 2318的题解 ,这道题只需注意以上两个坑点就很容易了,再给出这道题的代码。

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int N = 50001;
int n,m;
int u[N],l[N];
int ans[N],an[N],bn[N];
int x1,x2,y1,y2;
struct point
{
    int x,y;
}a[N];
struct line
{
    int u,v;
}b[N];
bool cmp1(point a,point b)
{
    return a.x<b.x;
}
bool cmp2(line c,line d)
{
    return c.u<d.u;
}
int xmul(int x1,int y1,int x2,int y2)
{
    return (x1*y2)-(x2*y1);
}
int main()
{
    while(cin>>n,n)
    {
        cin>>m>>x1>>y1>>x2>>y2;
        for(int i=0;i<n;i++)
        {
            cin>>b[i].u>>b[i].v;
            ans[i]=0;
        }
        ans[n]=0;
        sort(b,b+n,cmp2);
        for(int i=0;i<m;i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        sort(a,a+m,cmp1);
        for(int i=0,j;i<m;i++)
        {
            for(j=0;j<n;j++)
                if(xmul(a[i].x-b[j].v,a[i].y-y2,b[j].u-b[j].v,y1-y2)<=0)
                    break;
            ++ans[j];
        }
        for(int i = 1;i <= n;i++)
            an[i] = 0;
        for(int i = 0;i <= n;i++)
            if(ans[i]>0)
                an[ans[i]]++;
        printf("Box\n");
        for(int i = 1;i <= n;i++)
            if(an[i]>0)
                printf("%d: %d\n",i,an[i]);
    }
    return 0;
}
本文作者:Author:     文章标题:POJ 2398 Toy Storage(计算几何)
本文地址:https://alphalrx.cn/index.php/archives/48/     
版权说明:若无注明,本文皆为“LRX's Blog”原创,转载请保留文章出处。
Last modification:November 2nd, 2019 at 02:36 pm
给作者赏一杯奶茶吧!

Leave a Comment