uva1606 Amphiphilic Carbon Molecules

题目的主要思想在于依次选定一个节点，然后再选定剩下的另外一个节点，然后判断以这两个节点确定的直线作为边界，相应的黑色节点的个数以及白色节点的个数的最大值，这里也使用了一个很重要的方法，将黑色节点的位置进行中心对称，这样就将求解白色节点以及黑色节点的个数统一起来了，直接求出节点数然后取最大值就行了，具体实现见如下代码：

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<deque>
#include<functional>
using namespace std;

const int maxn = 1005;
int N;

typedef struct node{
	double x, y;
	double rad;
}node;

bool compare(const node a,const node b){
	return a.rad < b.rad;
}

int x[maxn], y[maxn], color[maxn], ans;

bool isLeft(node a,node b){//由a旋转到b
	return a.x*b.y - a.y*b.x >= 0;
}

void deal(){
	for (int i = 0; i < N; i++){
		vector<node> v;
		for (int j = 0; j < N; j++){
			if (j != i){
				node temp;
				temp.x = x[j] - x[i];
				temp.y = y[j] - y[i];
				if (color[j]){
					temp.x = -temp.x, temp.y = -temp.y;
				}
				temp.rad = atan2(temp.y, temp.x);
				v.push_back(temp);
			}
		}
		sort(v.begin(), v.end(), compare);
		int L = 0, R = 0;
		int amount = 2, up = v.size();
		while (L < up){
			if (L == R){
				R = (R + 1) % up;
				amount++;
			}
			while (R != L&&isLeft(v[L], v[R])){
				R = (R + 1) % up;
				amount++;
			}
			L++;
			amount--;
			ans = max(ans, amount);
		}
	}
}

int main(){ 
	while (cin >> N){
		if (N == 0) break;
		for (int i = 0; i < N; i++){
			cin >> x[i] >> y[i] >> color[i];
		}
		ans = -1;
		deal();
		cout << ans << endl;
	}
	return 0;
}