首页 > 代码库 > 【计算几何】【极角排序】【二分】Petrozavodsk Summer Training Camp 2016 Day 6: Warsaw U Contest, XVI Open Cup Onsite, Sunday, August 28, 2016 Problem J. Triangles
【计算几何】【极角排序】【二分】Petrozavodsk Summer Training Camp 2016 Day 6: Warsaw U Contest, XVI Open Cup Onsite, Sunday, August 28, 2016 Problem J. Triangles
平面上给你n(不超过2000)个点,问你能构成多少个面积在[A,B]之间的Rt三角形。
枚举每个点作为直角顶点,对其他点极角排序,同方向的按长度排序,然后依次枚举每个向量,与其对应的另一条直角边是单调的,可以用一个pointer做出来,然后可以得出那些同方向的向量的区间(这个代码好像有点问题,可能会退化,最好确定了一个LL之后,对一个方向的不要重复算RR。这里如果也改成二分就比较好,复杂度不会退化)。然后通过二分可以得到A使得面积在[A,B]间的有哪些(其实这个因为也是单调的,好像也没必要二分,不过二分也不影响)。
Hint:极角排序通过讨论所在象限以及叉积,可以避免使用atan2造成精度误差。atan2貌似只能处理坐标在几千内的情况。
O(n^2logn)
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll ans; struct Point{ ll x,y; int xx; ll l; Point(){} Point(const ll &x,const ll &y){ this->x=x; this->y=y; } void read(){ scanf("%lld%lld",&x,&y); } ll leng2(){ return x*x+y*y; } }a[2005],p[4005]; typedef Point Vector; Vector operator - (const Point &a,const Point &b){ return Vector(a.x-b.x,a.y-b.y); } bool cmp(const Point &a,const Point &b){ if(a.xx!=b.xx){ return a.xx<b.xx; } if(a.x*b.y != a.y*b.x){ return a.x*b.y > a.y*b.x; } return a.l<b.l; } ll dot(const Vector &a,const Vector &b){ return a.x*b.x+a.y*b.y; } ll Abs(const ll &x){ return x<0 ? (-x) : x; } ll area(const Vector &a,const Vector &b){ return Abs(a.x*b.y-a.y*b.x); } ll Cross(const Vector &a,const Vector &b){ return a.x*b.y-a.y*b.x; } ll A,B; int n,e; int main(){ // freopen("j.in","r",stdin); // freopen("j.out","w",stdout); scanf("%d%lld%lld",&n,&A,&B); for(int i=1;i<=n;++i){ a[i].read(); } for(int i=1;i<=n;++i){ e=0; for(int j=1;j<=n;++j){ if(j!=i){ p[++e]=a[j]-a[i]; if(p[e].x>0 && p[e].y>=0){ p[e].xx=1; } else if(p[e].x<=0 && p[e].y>0){ p[e].xx=2; } else if(p[e].x<0 && p[e].y<=0){ p[e].xx=3; } else{ p[e].xx=4; } p[e].l=p[e].leng2(); } } sort(p+1,p+e+1,cmp); for(int j=e+1;j<=2*e;++j){ p[j]=p[j-e]; } e<<=1; int LL=1; for(int j=1;j<=e/2;++j){ while(dot(p[LL],p[j])>0 && Cross(p[LL],p[j])<=0 && LL<j+e/2){ ++LL; } if(dot(p[LL],p[j])!=0 || Cross(p[LL],p[j])>0){ continue; } int RR=LL; while(Cross(p[RR],p[LL])==0 && dot(p[RR],p[LL])>0){ ++RR; } if(RR>LL){ if(area(p[LL],p[j])<=2ll*A-1ll){ int l=LL,r=RR-1; while(l<r){ int mid=(l+r+1>>1); if(area(p[mid],p[j])<=2ll*A-1ll){ l=mid; } else{ r=mid-1; } } ans-=(ll)(l-LL+1); } if(area(p[LL],p[j])<=2ll*B){ int l=LL,r=RR-1; while(l<r){ int mid=(l+r+1>>1); if(area(p[mid],p[j])<=2ll*B){ l=mid; } else{ r=mid-1; } } ans+=(ll)(l-LL+1); } } } } printf("%lld\n",ans); return 0; }
【计算几何】【极角排序】【二分】Petrozavodsk Summer Training Camp 2016 Day 6: Warsaw U Contest, XVI Open Cup Onsite, Sunday, August 28, 2016 Problem J. Triangles
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。