首页 > 代码库 > 【计算几何】【凸包】【极角排序】【二分】Gym - 101128J - Saint John Festival
【计算几何】【凸包】【极角排序】【二分】Gym - 101128J - Saint John Festival
平面上n个红点,m个黑点,问你多少个黑点至少在一个红三角形内。
对红点求凸包后,转化为询问有多少个黑点在凸包内。
点在凸多边形内部判定,选定一个凸包上的点作原点,对凸包三角剖分,将其他的点极角排序之后,使用二分法就可以判定点在哪个剖分出来的三角形的夹角内,然后用叉积即可判定其在凸包内还是外,O(logn):
http://www.cnblogs.com/dream-wind/archive/2012/05/23/2514694.html
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; int n,m,K,O; struct Point{ ll x,y; double jiao; Point(){} Point(const ll &x,const ll &y){ this->x=x; this->y=y; } void Read(){ scanf("%lld%lld",&x,&y); } }; typedef Point Vector; Point p0,p; Vector operator - (const Point &a,const Point &b){ return Vector(a.x-b.x,a.y-b.y); } ll Cross(const Vector &a,const Vector &b){ return a.x*b.y-a.y*b.x; } bool cmp(const Point &a,const Point &b){ return a.x!=b.x ? a.x<b.x : a.y<b.y; } bool cm2(const Point &a,const Point &b){ return a.jiao<b.jiao; } Point ps[10010],qs[10010]; bool check(int mid){ return Cross(qs[mid]-p0,p-p0)<=0; } int main(){ // freopen("j.in","r",stdin); scanf("%d",&n); for(int i=0;i<n;++i){ ps[i].Read(); } sort(ps,ps+n,cmp); for(int i=0;i<n;++i){ while(K>1 && Cross(qs[K-1]-qs[K-2],ps[i]-qs[K-1])<=0){ --K; } qs[K++]=ps[i]; } for(int i=n-2,t=K;i>=0;--i){ while(K>t && Cross(qs[K-1]-qs[K-2],ps[i]-qs[K-1])<=0){ --K; } qs[K++]=ps[i]; } --K; for(int i=1;i<K;++i){ if(qs[i].y<qs[O].y || (qs[i].y==qs[O].y && qs[i].x<qs[O].x)){ O=i; } } p0=qs[O]; for(int i=0;i<K;++i){ qs[i].jiao=atan2((double)(qs[i].y-qs[O].y),(double)(qs[i].x-qs[O].x)); } for(int i=O;i<K-1;++i){ qs[i]=qs[i+1]; } --K; sort(qs,qs+K,cm2); scanf("%d",&m); int ans=0; for(int i=1;i<=m;++i){ p.Read(); if(Cross(p-p0,qs[0]-p0)<=0 && Cross(p-p0,qs[K-1]-p0)>=0){ int l=1,r=K-1; while(l<r){ int mid=(l+r>>1); if(check(mid)){ r=mid; } else{ l=mid+1; } } if(Cross(p-qs[l-1],qs[l]-qs[l-1])<=0){ ++ans; } } } printf("%d\n",ans); return 0; }
【计算几何】【凸包】【极角排序】【二分】Gym - 101128J - Saint John Festival
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。