hdu5784 极角排序+two point
题意：
给定平面内若干点，要求求出这些点组成的三角形中锐角三角形的个数。
思路：
锐角三角形，即这个三角形中不存在直角或者钝角。所以现在的思路是不断枚举三个点，看他们之间组成的角度在什么范围内，这样的复杂O（n*n*n），时限内肯定不能通过。对于二维平面的向量，用点积和叉积可以较为方便的判断他们之间的角度。
由于 锐角三角形个数=三角形个数-直角个数-顿角个数
可以考虑枚举每一个点，以这个点为参考点，对这个点和其他点组成的向量进行极角排序，这个在一个相对有序的向量之间，判断两两之间的角度就可以优化了，存在二分的two point两种优化方法，two point较为好写。如何尺取呢？由于向量之间有序，对于某个向量i，用p1取到最大的钝角，p2取到最大的锐角，p1-p2就是这些向量与i成直角和钝角的个数了。然后i->i+1,此时的p1和p2可以保持不动，two point 为O（n)。由于第四象限的向量和第一象限可以组成锐角，需要把排序的向量数组首尾连接。
对于极角相同向量，不能构成三角形，只需要遍历向量数组，找到重复的个数。由于n次遍历存在重复，最后要取一半。
最后总的时间复杂度为O（n*n*logn）。
代码：
1 #include <iostream> 2 #include<algorithm> 3 #include<cmath> 4 #define ll long long 5 using namespace std; 6 const int N=2005; 7 const double pi=acos(-1.0); 8 struct point{ 9 ll x,y; 10 }po[N]; 11 double p[2*N]; 12 int n; 13 int main() 14 { 15 cout<<atan2(1,1)<<" :atan(1,1)"<<endl; 16 cout<<atan2(-1,1)<<" :atan(-1,1)"<<endl; 17 cout<<atan2(-1,-1)<<" :atan(-1,-1)"<<endl; 18 cout<<atan2(1,-1)<<" :atan(1,-1)"<<endl; 19 while(~scanf("%d",&n)){ 20 ll ans=1LL*n*(n-1)*(n-2)/6; 21 ll temp=0; 22 for(int i=0;i<n;i++){ 23 scanf("%lld%lld",&po[i].x,&po[i].y); 24 } 25 for(int i=0;i<n;i++){ 26 int cnt=0; 27 for(int j=0;j<n;j++){ 28 if(i!=j)p[cnt++]=atan2(po[j].y-po[i].y,po[j].x-po[i].x); 29 if(p[cnt-1]<0)p[cnt-1]+=2*pi; 30 } 31 sort(p,p+cnt); 32 for(int j=0;j<cnt;j++)p[j+cnt]=p[j]+2*pi; 33 34 ll num=0; 35 for(int j=1;j<cnt;j++){ 36 if(p[j]==p[j-1])num++; 37 else num=0; 38 temp+=num; 39 } 40 int p1=0,p2=0; 41 for(int j=0;j<cnt;j++){ 42 while(p1<=j||(p1<2*cnt&&p[p1]-p[j]<pi))p1++; 43 while(p2<j||(p2<2*cnt&&p[p2]-p[j]<pi/2))p2++; 44 ans-=p1-p2; 45 } 46 } 47 cout<<ans-temp/2<<endl; 48 } 49 return 0; 50 }
查看6道真题和解析
投递嘉士伯等公司10个岗位 >