频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 2318 TOYS
2015-03-03 14:57:51         来源:最光阴的专栏  
收藏   我要投稿

这题计算几何的部分还是比较简单的,重点是那个二分有点麻烦(大牛忽略),每次写二分自己都得用笔模拟一番,然后才能确定。

因为y1,y2是公共的,所以存储的时候线段的时候只要存储x的坐标就可以了。然后就是判断是在右边还是在左边。

#include
#include
#include
#include
using namespace std;
const int N=5005;
struct Line
{
    int x1,x2;
}line[N];
int x1,x2,y1,y2,n,m,num[N];
int judge(int x,int y,int id)
{
   int a1=line[id].x1-x,a2=line[id].x2-x;
   int b1=y1-y,b2=y2-y;
   return a1*b2-a2*b1;
}
int main()
{
    int x,y,k=0;
    while(scanf("%d",&n),n!=0)
    {
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&line[i].x1,&line[i].x2);
        memset(num,0,sizeof(num));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            if(judge(x,y,1)<0)//这里要注意一下
            {
                num[0]++;
                continue;
            }
            if(judge(x,y,n)>0)//这里也要注意,通过画图可以发现,这里需要单独讨论一下。
            {
                num[n]++;
                continue;
            }
            int l=1,r=n;//这里是二分
            while(r-l>1)
            {
                int mid=(l+r)/2;
                if(judge(x,y,mid)<0)
                    r=mid;
                else
                    l=mid;
            }
            num[l]++;
        }
        if(k>0)
            printf("\n");
        k++;
        for(int i=0;i<=n;i++)
            printf("%d: %d\n",i,num[i]);
    }
    return 0;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:CodeForces 520D Cubes
下一篇:LeetCode --- 46. Permutations
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站