从TLE的暴力枚举 到 13313MS的扫描线 再到 1297MS的简化后的扫描线，简直感觉要爽翻啦。然后满怀欣喜的去HDU交了一下，直接又回到了TLE.....泪流满面
虽说HDU的时限是2000MS 可是数据也忒强了点吧，真心给HDU跪了。
题意：给定平面上的N个点，属性分别标记为0和1，然后找一条直线，直线上的点全部溶解，一侧的1溶解，另一侧的0溶解。求出最多能溶解的点的个数。
思路：最直接的思路就是O(N^3)的暴力枚举，Discuss里面貌似有大牛过了，肯能是我太过暴力了吧，果断Tle了，然后换成了枚举单个点，然后极角排序+扫描线，
跑了13313MS。然后优化了一下跑了1297MS。下面说一下扫描线的思路。
首先，确定射线v1，v2与X轴正方向的角度，一个为0，一个为PI，然后同时旋转，每碰到一个点就计算一次v1，v2之间的及在两条射线上的点。
直到v1与X轴的方向 >= PI ,当前这一次计算结束，继续枚举下一个点。
这就是13313MS那份代码的思路，显然扫描线是没错的，但是有一些点被重复计算了，其实我们只需要计算α角区域内的点的个数，通过它来维
护v1，v2区域内的点的个数，优化后用时就减少到了1297MS，但是在HDU依然过不了......
POJ AC_Code 1297MS
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string> #define LL long long
#define EPS (1e-8) using namespace std; const double PI = acos(-1.0); struct P
{
double a;
int x,y,mark;
} pa[1010],p[1010]; double Cal_Angle(P p1,P p2)
{
if(p1.x == p2.x && p1.y == p2.y)
return -100.0;
P v;
v.x = p2.x - p1.x;
v.y = p2.y - p1.y;
if(p1.y <= p2.y)
return acos(v.x/sqrt(v.x*v.x + v.y*v.y));
return 2.0*PI - acos(v.x/sqrt(v.x*v.x + v.y*v.y));
} void Cal_Angle(P p,P *pa,int n)
{
for(int i = 0; i < n; ++i)
{
pa[i].a = Cal_Angle(p,pa[i]);
}
} bool cmp_angle(P p1,P p2)
{
return p1.a < p2.a;
} int main()
{
int n,i,j,k,l,d;
int Max,tl,tr,b,w,s1,s0,s2,s3;
double xm,pil,pir;
P vec;
while(scanf("%d",&n) && n)
{
b = 0;
w = 0;
for(i = 0; i < n; ++i)
{
scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].mark);
pa[i] = p[i];
if(pa[i].mark)
b++;
else
w++;
} Max = -1; for(i = 0; i < n; ++i)
{
Cal_Angle(p[i],pa,n);
sort(pa,pa+n,cmp_angle); pir = pa[1].a;
pil = pir + PI; s1 = s0 = s2 = s3 = 0; for(j = 1; j < n && pa[j].a < pil; ++j)
{
if(pa[j].a == pir)
{
if(pa[j].mark)
s3++;
else
s2++;
}
else
{
if(pa[j].mark)
s1++;
else
s0++;
}
} for(d = j; d < n && pa[d].a == pil; ++d)
{
if(pa[d].mark)
s3++;
else
s2++;
} if(pa[0].mark)
s3++;
else
s2++; tr = s0 + (b-s1)+s2;
tl = s1 + (w-s0)+s3; if(tr > Max || tl > Max)
Max = tr > tl ? tr : tl; k = 1; while(pir < PI && j < n)
{
for(; k < n && pir == pa[k].a; ++k)
{
if(pa[k].mark)
--s3;
else
--s2;
}
pir = pa[k].a;
if(pir > PI)
break;
for(l = k; l < n && pir == pa[l].a; ++l)
{
if(pa[l].mark)
{
++s3;
--s1;
}
else
{
++s2;
--s0;
}
}
for(; j < n && pa[j].a == pil; ++j)
{
if(pa[j].mark)
{
--s3;
++s1;
}
else
{
--s2;
++s0;
}
} pil = pir+PI; for(; j < n && pa[j].a < pil; ++j)
{
if(pa[j].mark)
{
++s1;
}
else
{
++s0;
}
} for(d = j; d < n && pa[d].a == pil ; ++d)
{
if(pa[d].mark)
++s3;
else
++s2;
}
tr = s0 + (b-s1)+s2;
tl = s1 + (w-s0)+s3;
if(tr > Max || tl > Max)
{
Max = tr > tl ? tr : tl;
}
}
}
printf("%d\n",Max);
}
return 0 ;
}
POJ AC_Code 13313MS
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string> #define LL long long
#define EPS (1e-8) using namespace std; const double PI = acos(-1); struct P
{
double x,y,a;
int mark;
}pa[1010],p[1010]; double Cal_Angle(P p1,P p2)
{
if(p1.x == p2.x && p1.y == p2.y)
return -100.0;
P v;
v.x = p2.x - p1.x;
v.y = p2.y - p1.y;
if(p1.y <= p2.y)
return acos(v.x/sqrt(v.x*v.x + v.y*v.y));
return 2.0*PI - acos(v.x/sqrt(v.x*v.x + v.y*v.y));
} void Cal_Angle(P p,P *pa,int n)
{
for(int i = 0;i < n; ++i)
{
pa[i].a = Cal_Angle(p,pa[i]);
}
} bool cmp_angle(P p1,P p2)
{
return p1.a < p2.a;
} int main()
{
int n,i,j,k;
int tm1,tm0,tm2,tm3,Max,t1,t2,b,w;
double xm,pil,pir;
P vec;
while(scanf("%d",&n) && n)
{
b = 0;
w = 0;
for(i = 0;i < n; ++i)
{
scanf("%lf %lf %d",&p[i].x,&p[i].y,&p[i].mark);
pa[i] = p[i];
if(pa[i].mark)
b++;
else
w++;
} Max = -1; for(i = 0;i < n; ++i)
{
Cal_Angle(p[i],pa,n);
sort(pa,pa+n,cmp_angle);
pir = pa[0].a;
j = 1;
while(pir <= PI && j < n)
{
for(;j < n && pa[j].a == pir; ++j)
;
pir = pa[j].a; tm3 = 0;
tm2 = 0;
tm1 = 0;
tm0 = 0; for(pil = pir+PI,k = j;pa[k].a < pil && k < n; ++k)
{
if(pa[j].a == pa[k].a)
{
if(pa[k].mark == 1)
{
tm3 ++;
}
else
{
tm2 ++;
}
}
else if(pa[k].mark == 0)
{
tm0++;
}
else
{
tm1++;
}
}
if(pa[0].mark)
tm3++;
else
tm2++;
t1 = tm1+tm2+tm3 + (w-tm0-tm2);
t2 = tm0+tm2+tm3 + (b-tm1-tm3);
if(Max < t1 || Max < t2)
{
Max = t1 > t2 ? t1 : t2;
}
}
}
printf("%d\n",Max);
}
return 0 ;
}