首页 > 其他 > 详细

SGU-253 Theodore Roosevelt

时间:2020-01-22 09:47:01      阅读:95      评论:0      收藏:0      [点我收藏+]

题意:

题目链接
给一个\(n\)边形(凸多边形),再给出\(m\)个点,求有多少个点落在多边形内部(含边界),点的坐标均为整数\(n,m<=2*10^5\)

思路:

数据范围较大,不能一条边一条边枚举
考虑二分。而后用叉积解决。
因为本题多边形为逆时针给出,因此基准点随便选。

注意事项:

考虑点在某条边上,那么二分到此处时叉积为0
但是要注意,如果该点在这条边所在直线上,那么叉积也为0,要特判一下
还有,因为有叉乘,所以要开long long

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,k,pos,mn=1e9,ans;
struct point{long long x,y;long long dis(){return x*x+y*y;}}b[N];
point operator-(point x,point y){return (point){x.x-y.x,x.y-y.y};}
long long operator^(point x,point y){return x.x*y.y-x.y*y.x;}
inline int read()
{
    int s=0,w=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return s*w;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;++i)
        b[i].x=read(),b[i].y=read();
    while(m--)
    {
        point u;
        u.x=read(),u.y=read();
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(((b[mid]-b[1])^(u-b[1]))<0)r=mid-1;
            else l=mid;
        }
        r=(l==n?1:l+1);
        long long e=(b[l]-u)^(b[r]-u);
        if(e>0)++ans;
        else if(e==0)
        {
            long long dist=(b[l]-b[r]).dis();
            if((b[l]-u).dis()<=dist&&(b[r]-u).dis()<=dist)++ans;
        }
    }
    if(ans>=k) puts("YES");
    else puts("NO");
    return 0;
}

SGU-253 Theodore Roosevelt

原文:https://www.cnblogs.com/zmyzmy/p/12227905.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!