首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。