首页 > 代码库 > poj2280Amphiphilic Carbon Molecules(极角排序)

poj2280Amphiphilic Carbon Molecules(极角排序)

链接

卡了几天的破题,对于hdu的那份数据,这就一神题。。

借助极角排序,枚举以每一个点进行极角排序,然后构造两条扫描线,一个上面一个下面,两条同时走,把上线和下线的点以及上线左边的点分别统计出来,如下图

样例3:

假如现在以d为p[0],那么所有可能结果一定是他与其他点的连线所分割的平面,那么首先以de为上线,下线的角度为上线+pi,两条线始终维护着这样的关系。de的下一个点为f,di的下一个点为c ,比较一下两者需要转的角度,选取较小角度转,注意一下相同的时候的处理。

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 1010 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     double x,y; 20     double a; 21     int flag; 22     point(double x=0,double y = 0):x(x),y(y) {} 23 } p[N],q[N]; 24 int tx[N],ty[N]; 25 typedef point pointt; 26 point operator -(point a,point b) 27 { 28     return point(a.x-b.x,a.y-b.y); 29 } 30 int dcmp(double x) 31 { 32     if(fabs(x)<eps) return 0; 33     return x<0?-1:1; 34 } 35 double cross(point a,point b) 36 { 37     return a.x*b.y-a.y*b.x; 38 } 39 double mul(point a,point b,point c) 40 { 41     return cross(b-a,c-a); 42 } 43 double dis(point a) 44 { 45     return sqrt(a.x*a.x+a.y*a.y); 46 } 47 int dot_online_in(point p,point l1,point l2) 48 { 49     return !dcmp(mul(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps; 50 } 51 double dot(point a,point b) 52 { 53     return a.x*b.x+a.y*b.y; 54 } 55 double Cal_Angle(point p1,point p2) 56 { 57     if(p1.x == p2.x && p1.y == p2.y) 58         return -100.0; 59     point v; 60     v.x = p2.x - p1.x; 61     v.y = p2.y - p1.y; 62     if(p1.y <= p2.y) 63         return acos(v.x/sqrt(dot(v,v))); 64     return 2.0*pi - acos(v.x/sqrt(dot(v,v))); 65 } 66  67 void Cal_Angle(point pp,point p[],int n) 68 { 69     for(int i = 0; i < n; ++i) 70     { 71         p[i].a = Cal_Angle(pp,p[i]); 72     } 73 } 74 bool cmp_angle(point p1,point p2) 75 { 76     return p1.a < p2.a; 77 } 78 int main() 79 { 80     int i,j,n; 81     while(scanf("%d",&n)&&n) 82     { 83         int a =0,b =0 ; 84         for(i = 0; i < n; i++) 85         { 86             scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].flag); 87             q[i] = p[i]; 88             if(p[i].flag) a++; 89             else b++; 90         } 91         if(n<3) 92         { 93             printf("%d\n",n); 94             continue; 95         } 96         int ans = max(a,b); 97         for(i = 0; i < n; i++) 98         { 99             swap(q[i],q[0]);100             for(j = 0 ; j < n; j++)101                 p[j] = q[j];102             Cal_Angle(p[0],p,n);103             sort(p+1,p+n,cmp_angle);104             for(j = n-1; j > 0 ; j--)105                 p[j].a-=p[1].a;106             double ani = p[1].a,anj = pi+ani;107             int on_red = 0,on_blue = 0,under_red = 0, under_blue = 0,red = 0,blue = 0;108             int g = 1;109             while(dcmp(p[g].a-ani)==0&&g<n)110             {111                 p[g++].flag?on_red++:on_blue++;112             }113             int tk = n;114             for(j = g; j < n; j++)115             {116                 if(dcmp(p[j].a-anj)>0)117                 {118                     tk = j;119                     break;120                 }121                 if(dcmp(p[j].a-anj)==0)122                 {123                     while(dcmp(p[j].a-anj)==0&&j<n)124                     {125                         p[j++].flag?under_red++:under_blue++;126                     }127                     tk = j;128                     break;129                 }130                 p[j].flag?red++:blue++;131             }132             int ta = 0,tb = 0;133             p[0].flag?ta++:tb++;134 135             int k1 = red+on_red+under_red+1+b-blue-tb;136             int k2 = blue+on_blue+under_blue+1+a-red-ta;137 138             ans = max(ans,max(k1,k2));139             if(g==n) continue;140 141             while(tk<n)142             {143                 red+=under_red,blue+=under_blue;144                 on_red = on_blue = under_blue = under_red = 0;145 146                 if(tk==n||p[tk].a-anj>p[g].a-ani)147                 {148                     ani = p[g].a;149                     anj = ani+pi;150                     while(dcmp(p[g].a-ani)==0&&g<n)151                     {152                         p[g].flag?on_red++:on_blue++;153                         p[g++].flag?red--:blue--;154                     }155                 }156                 else157                 {158                     anj = p[tk].a;159                     ani = anj-pi;160                     while(dcmp(p[tk].a-anj)==0&&tk<n)161                     {162                         p[tk++].flag?under_red++:under_blue++;163                     }164                     while(dcmp(p[g].a-ani)==0&&g<n)165                     {166                         p[g].flag?on_red++:on_blue++;167                         p[g++].flag?red--:blue--;168                     }169                 }170 171                 int k1 = red+on_red+under_red+1+b-blue-tb;172                 int k2 = blue+on_blue+under_blue+1+a-red-ta;173                 ans = max(ans,max(k1,k2));174             }175         }176         printf("%d\n",ans);177     }178     return 0;179 }
View Code