题意:平面上有n(n <= 1000)个点,每个点为白点或者黑点。现在需放置一条隔板,使得隔板一侧的白点数加上另一侧的黑点数总数最大。隔板上的点可以看做是在任意一侧。
分析:枚举每个基准点i,将一条直线绕这个点旋转,每当扫过一个点,就可以动态修改两侧的点数。
对于--sum,
1、如果while循环是因为s==j退出的,则其减的是if(s == j)时暂且多加上去的一个sum,这种情况是,所有的点都在基准线的左边。
2、如果while循环是因为!left(vec[j], vec[s])退出的,则其减的是因为基准线移动,上一个与基准点相连的点已不在基准线左边的情况,这种情况同样适用于旋转基准线但是没有新增点,所有sum自然会减少。
3、本题技巧是将黑点旋转180°,这样就可以化统计一侧白点和一侧黑点为统计一侧点的数量的问题。
#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int MAXN = 1000 + 10;
const int MAXT = 10000 + 10;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
using namespace std;
int n;
struct Point{
int x, y, color;
double angle;
void read(){
scanf("%d%d%d", &x, &y, &color);
}
void Set(int xx, int yy, int cc){
x = xx;
y = yy;
if(cc){//如果为黑点,则相对于基准点旋转180°
x = -x;
y = -y;
}
angle = atan2(y, x);
}
bool operator<(const Point& rhs)const{
return dcmp(angle, rhs.angle) == -1;
}
}p[MAXN], vec[MAXN];
bool left(Point A, Point B){
return A.x * B.y - B.x * A.y >= 0;//叉乘
}
int solve(){
if(n <= 3) return n;
int ans = 0;
for(int i = 0; i < n; ++i){//基准点i
int cnt = 0;
for(int j = 0; j < n; ++j){
if(i != j){
vec[cnt++].Set(p[j].x - p[i].x, p[j].y - p[i].y, p[j].color);//点j相对于基准点i的相对坐标
}
}
sort(vec, vec + cnt);
int sum = 2;
int s = 0;//扫描射线
for(int j = 0; j < cnt; ++j){//以基准点为原点,枚举所有经过除基准点之外的点的射线
if(s == j){
(s += 1) %= cnt;
++sum;
}
while(s != j && left(vec[j], vec[s])){
(s += 1) %= cnt;
++sum;
}
--sum;
ans = Max(ans, sum);
}
}
return ans;
}
int main(){
while(scanf("%d", &n) == 1){
if(!n) return 0;
for(int i = 0; i < n; ++i){
p[i].read();
}
printf("%d\n", solve());
}
return 0;
}