题意：给定平面上的N个点，属性分别标记为0和1，然后找一条直线，直线上的点全部溶解，一侧的1溶解，另一侧的0溶解。求出最多能溶解的点的个数。
思路：暴力枚举每个点，扫描线旋转。先做优化，如果一侧溶解0，则把属性为1的做关于当前枚举直线对称的点，这样统计一侧的点加上线上的点就是答案。O(n2).
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<set> 6 #include<stdio.h> 7 #include<stdlib.h> 8 #include<math.h> 9 #define clc(a,b) memset(a,b,sizeof(a)) 10 #define eps 1e-8 11 typedef long long LL; 12 const int mod=47000; 13 const int inf=0x3f3f3f3f; 14 using namespace std; 15 #define N 100010 16 17 struct node 18 { 19 int x,y,r; 20 double ang; 21 }v[1010],rem[1010]; 22 23 int cmp(const struct node a,const struct node b) 24 { 25 if(a.ang<b.ang) 26 return 1; 27 else 28 return 0; 29 } 30 31 int sig (double a) 32 { 33 if(fabs(a)<eps) 34 return 0; 35 else if(a>0) 36 return 1; 37 else 38 return -1; 39 } 40 41 int cross(struct node a,struct node b,struct node c) 42 { 43 return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); 44 } 45 46 int main() 47 { 48 int n; 49 while(~scanf("%d",&n)&&n) 50 { 51 int ans=0; 52 for(int i=0;i<n;i++) 53 { 54 scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].r); 55 rem[i]=v[i]; 56 } 57 for(int i=0;i<n;i++) 58 { 59 for(int j=0;j<n;j++) 60 { 61 v[j]=rem[j]; 62 if(v[j].r==1) 63 { 64 v[j].x=rem[i].x*2-v[j].x; 65 v[j].y=rem[i].y*2-v[j].y; 66 } 67 v[j].ang=atan2(v[j].y-rem[i].y,v[j].x-rem[i].x); 68 } 69 swap(v[i],v[0]); 70 sort(v+1,v+n,cmp); 71 for(int j=1,t=2;j<n&&sig(v[j].ang)<=0;j++) 72 { 73 int on=2; 74 for( ;t<n&&cross(v[0],v[j],v[t])>=0;t++) 75 { 76 if(cross(v[0],v[j],v[t])==0) 77 on++; 78 } 79 ans=max(ans,max(t-j+1,n-(t-j+1)+on)); 80 } 81 } 82 cout<<ans<<endl; 83 } 84 return 0; 85 }