561_500

用stl的complex挺方便的，记住这几个函数就够用了

arg(t);返回值(-pi, pi]

real(t);

imag(t);

abs(t);

 

然后把complex的除法运算优化成乘法运算，效率就够用了。

 

const double pi = acos(-1.0);
const double eps = 1e-9;

typedef complex<double> cd;
//在这里定义vector可以减少局部变量开辟回收的开销
vector<double> w0, w1, d0, d1;
bool hasIt(cd t0, cd t1, const vector<cd>& vc) {
	w0.clear();
	w1.clear();
	d0.clear();
	d1.clear();
	//除法优化好关键，否则常数太大
	cd tt = cd(1, 0) / (t1 - t0);
	for (int i = 0; i < vc.size(); ++i) {
		cd c0 = (vc[i] - t0) * tt;
		cd c1 = (vc[i] - t1) * tt;
		double x0 = arg(c0), x1 = arg(c1);
		if (x0 > 0) {
			w0.push_back(x0);
			w1.push_back(x1);
		} else {
			d0.push_back(x0 + pi);
			d1.push_back(x1 + pi);
		}
	}
	sort(w0.begin(), w0.end());
	sort(w1.begin(), w1.end());
	for (int i = 0; i < d0.size(); ++i) {
		int a0 = lower_bound(w0.begin(), w0.end(), d0[i]) - w0.begin();
		int a1 = lower_bound(w1.begin(), w1.end(), d1[i]) - w1.begin();
		if (a0 != a1) return true;
	}
	return false;
}

class CheckerFreeness {
public:
    string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY) {
        vector<cd> v1, v2;
		vector<double> t0, t1, t2, t3;
		Scanf(whiteX, t0);
		Scanf(whiteY, t1);
		Scanf(blackX, t2);
		Scanf(blackY, t3);
		for (int i = 0; i < t0.size(); ++i) v1.push_back(cd(t0[i], t1[i]));
		for (int i = 0; i < t2.size(); ++i) v2.push_back(cd(t2[i], t3[i]));
		for (int i = 0; i < v1.size(); ++i) {
			for (int j = i + 1; j < v1.size(); ++j) {
				if (hasIt(v1[i], v1[j], v2)) return "NO";
			}
		}
		return "YES";
    }
};