卡了几天的破题，对于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); 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 else 157 { 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 ",ans); 177 } 178 return 0; 179 }