任意线可以贪心移动到两点上。直接枚举O（n^3），会TLE。
所以采取扫描法，选基准点，然后根据极角或者两两做叉积比较进行排排序，然后扫一遍就好了。旋转的时候在O（1）时间推出下一种情况，总复杂度为O（n^2logN）就可以过了。
另外，本题有个很巧妙的技巧，就是一点等效与相反坐标的相反颜色的点。
第一次写，细节还是蛮多的，花了好久才搞清所有细节。。。
极角排序版，比较容易理解，932ms。
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
struct Point
{
int x,y;
double rad;
bool operator<(const Point &rhs) const {
return rad < rhs.rad;
}
}P[maxn];
int col[maxn]; Point tmp[maxn]; bool cmp(const Point& a,const Point& b) //anticlockwise sort
{
return a.x*b.y >= b.x*a.y;
} int solve(int n)
{
if(n<=) return n;
int ans = -;
for(int pivot = ; pivot < n; pivot++){
int k = ;
for(int i = ; i < n; i++) if(i!=pivot){
tmp[k].x = P[i].x - P[pivot].x;
tmp[k].y = P[i].y - P[pivot].y;
if(col[i]) { tmp[k].x = - tmp[k].x; tmp[k].y = -tmp[k].y; }
tmp[k].rad = atan2(tmp[k].y, tmp[k].x);
k++;
}
sort(tmp,tmp+k);
int L = , R = , sum = ;
while(L<k){
if(L == R) { R = (R+)%k; sum++; }
while(R != L && cmp(tmp[L],tmp[R])) {
R = (R+)%k; sum++;
}
ans = max(ans,sum);
sum--; L++;
}
}
return ans;
} int main()
{
int n;
while(~scanf("%d",&n)&&n){
for(int i = ; i < n; i++)
scanf("%d%d%d",&P[i].x,&P[i].y,col+i);
printf("%d\n",solve(n));
}
return ;
}
极角排序
如果卡精度，那么就用叉积两两比较，算极角常数大一些，叉积跑的快一点577ms。
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
struct Point
{
int x,y,col;
}P[maxn],tmp[maxn];; inline int cross(const Point& a,const Point& b)
{
return a.x*b.y - b.x*a.y;
} bool cmp(const Point& a,const Point& b) //anticlockwise sort
{
return a.x*b.y > b.x*a.y;
} int solve(int n)
{
if(n<=) return n;
int ans = -;
for(int pivot = ; pivot < n; pivot++){
int k = ;
for(int i = ; i < n; i++) if(i!=pivot){
tmp[k].x = P[i].x - P[pivot].x;
tmp[k].y = P[i].y - P[pivot].y;
if(tmp[k].y < || (tmp[k].y == && tmp[k].x < ) ) {
tmp[k].x = - tmp[k].x; tmp[k].y = -tmp[k].y;
tmp[k].col = P[i].col^;
}else tmp[k].col = P[i].col;
k++;
}
sort(tmp,tmp+k,cmp);
int w = ,b = ;
int i,j;
for(i = ; i < k; i++) if(tmp[i].col == )w++;
for( i = ; i < k; i = j) {
int lw = ;
for(j = i; j < k; j++) {
if(cross(tmp[i],tmp[j])) break;
if(tmp[j].col) b++;
else lw++;
}
ans = max(ans,w+b+);
ans = max(ans,k-w-b+j-i+);
w -= lw;
}
}
return ans;
} int main()
{
int n;
while(~scanf("%d",&n)&&n){
for(int i = ; i < n; i++)
scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].col);
printf("%d\n",solve(n));
}
return ;
}
叉积