155c399d58 2012-12-08        kinaba: #include <iostream>
155c399d58 2012-12-08        kinaba: #include <sstream>
155c399d58 2012-12-08        kinaba: #include <iomanip>
155c399d58 2012-12-08        kinaba: #include <vector>
155c399d58 2012-12-08        kinaba: #include <string>
155c399d58 2012-12-08        kinaba: #include <map>
155c399d58 2012-12-08        kinaba: #include <set>
155c399d58 2012-12-08        kinaba: #include <algorithm>
155c399d58 2012-12-08        kinaba: #include <numeric>
155c399d58 2012-12-08        kinaba: #include <iterator>
155c399d58 2012-12-08        kinaba: #include <functional>
155c399d58 2012-12-08        kinaba: #include <complex>
155c399d58 2012-12-08        kinaba: #include <queue>
155c399d58 2012-12-08        kinaba: #include <stack>
155c399d58 2012-12-08        kinaba: #include <cmath>
155c399d58 2012-12-08        kinaba: #include <cassert>
155c399d58 2012-12-08        kinaba: using namespace std;
155c399d58 2012-12-08        kinaba: typedef long long LL;
155c399d58 2012-12-08        kinaba: typedef complex<double> CMP;
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: class CheckerFreeness { public:
155c399d58 2012-12-08        kinaba: 	string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY)
155c399d58 2012-12-08        kinaba: 	{
155c399d58 2012-12-08        kinaba: 		stringstream swx(accumulate(whiteX.begin(), whiteX.end(), string("")));
155c399d58 2012-12-08        kinaba: 		stringstream swy(accumulate(whiteY.begin(), whiteY.end(), string("")));
155c399d58 2012-12-08        kinaba: 		stringstream sbx(accumulate(blackX.begin(), blackX.end(), string("")));
155c399d58 2012-12-08        kinaba: 		stringstream sby(accumulate(blackY.begin(), blackY.end(), string("")));
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: 		vector<CMP> w;
155c399d58 2012-12-08        kinaba: 		for(int x,y; (swx>>x)&&(swy>>y); )
155c399d58 2012-12-08        kinaba: 			w.push_back(CMP(x,y));
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: 		vector<CMP> b;
155c399d58 2012-12-08        kinaba: 		for(int x,y; (sbx>>x)&&(sby>>y); )
155c399d58 2012-12-08        kinaba: 			b.push_back(CMP(x,y));
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: 		return has_checker(w,b) ? "NO" : "YES";
155c399d58 2012-12-08        kinaba: 	}
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: 	bool has_checker(const vector<CMP>& w, const vector<CMP>& b)
155c399d58 2012-12-08        kinaba: 	{
155c399d58 2012-12-08        kinaba: 		for(int i=0; i<w.size(); ++i)
155c399d58 2012-12-08        kinaba: 		for(int k=i+1; k<w.size(); ++k)
155c399d58 2012-12-08        kinaba: 			if(has_crosser(w[i], w[k], b))
155c399d58 2012-12-08        kinaba: 				return true;
155c399d58 2012-12-08        kinaba: 		return false;
155c399d58 2012-12-08        kinaba: 	}
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: 	bool has_crosser(CMP a, CMP b, const vector<CMP>& ps)
155c399d58 2012-12-08        kinaba: 	{
155c399d58 2012-12-08        kinaba: 		vector<double> arg_a, arg_b;
155c399d58 2012-12-08        kinaba: 		vector<CMP> qs;
155c399d58 2012-12-08        kinaba: 		for(int i=0; i<ps.size(); ++i)
155c399d58 2012-12-08        kinaba: 		{
155c399d58 2012-12-08        kinaba: 			double d = arg( (ps[i]-a)/(b-a) );
155c399d58 2012-12-08        kinaba: 			if(d > 0) {
155c399d58 2012-12-08        kinaba: 				arg_a.push_back(d);
155c399d58 2012-12-08        kinaba: 				d = arg( (ps[i]-b)/(b-a) );
155c399d58 2012-12-08        kinaba: 				arg_b.push_back(d);
155c399d58 2012-12-08        kinaba: 			} else {
155c399d58 2012-12-08        kinaba: 				qs.push_back(ps[i]);
155c399d58 2012-12-08        kinaba: 			}
155c399d58 2012-12-08        kinaba: 		}
155c399d58 2012-12-08        kinaba: 		sort(arg_a.begin(), arg_a.end());
155c399d58 2012-12-08        kinaba: 		sort(arg_b.begin(), arg_b.end());
155c399d58 2012-12-08        kinaba: 		for(int i=0; i<qs.size(); ++i)
155c399d58 2012-12-08        kinaba: 		{
155c399d58 2012-12-08        kinaba: 			CMP q = qs[i];
155c399d58 2012-12-08        kinaba: 			double aMax = arg((a-q) / (b-a));
155c399d58 2012-12-08        kinaba: 			double bMax = arg((b-q) / (b-a));
155c399d58 2012-12-08        kinaba: 			int aNum = lower_bound(arg_a.begin(), arg_a.end(), aMax) - arg_a.begin();
155c399d58 2012-12-08        kinaba: 			int bNum = lower_bound(arg_b.begin(), arg_b.end(), bMax) - arg_b.begin();
155c399d58 2012-12-08        kinaba: 			if(aNum != bNum)
155c399d58 2012-12-08        kinaba: 				return true;
155c399d58 2012-12-08        kinaba: 		}
155c399d58 2012-12-08        kinaba: 		return false;
155c399d58 2012-12-08        kinaba: 	}
155c399d58 2012-12-08        kinaba: };
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: // BEGIN CUT HERE
155c399d58 2012-12-08        kinaba: #include <ctime>
155c399d58 2012-12-08        kinaba: double start_time; string timer()
155c399d58 2012-12-08        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
155c399d58 2012-12-08        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
155c399d58 2012-12-08        kinaba:  { os << "{ ";
155c399d58 2012-12-08        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
155c399d58 2012-12-08        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
155c399d58 2012-12-08        kinaba: void verify_case(const string& Expected, const string& Received) {
155c399d58 2012-12-08        kinaba:  bool ok = (Expected == Received);
155c399d58 2012-12-08        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
155c399d58 2012-12-08        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
155c399d58 2012-12-08        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
155c399d58 2012-12-08        kinaba: #define END	 verify_case(_, CheckerFreeness().isFree(whiteX, whiteY, blackX, blackY));}
155c399d58 2012-12-08        kinaba: int main(){
155c399d58 2012-12-08        kinaba: 
155c399d58 2012-12-08        kinaba: CASE(0)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = {"1 2"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = {"2 1"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = {"1 2"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = {"1 2"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = "NO";
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: CASE(1)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = {"2", "5", "3", " ", "1", "7", "3"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = {"180 254"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = {"32", "5 1", "42"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = {"462 423"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = "YES";
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: CASE(2)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = {"1 10000000 9999999"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = {"1 9999999 1"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = {"2 5000000 9999998"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = {"2 5000001 9999999"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = "YES";
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: CASE(3)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = {"1"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = {"2"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = {"3"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = {"4"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = "YES";
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: CASE(4)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = {"6115 9723 3794 2275 2268 2702 3657 915 7953 2743 7"
155c399d58 2012-12-08        kinaba: ,"716 9645 2547 9490 9365 326 6601 5215 6771 7153 72"
155c399d58 2012-12-08        kinaba: ,"93 5922 714 2258 4369 9524 302 8417 6620 1143"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = {"621 1611 7140 503 5345 7202 681 4908 2510 5908 279"
155c399d58 2012-12-08        kinaba: ,"6 6286 6873 6682 9197 6710 8517 1913 7784 8533 665"
155c399d58 2012-12-08        kinaba: ,"4 446 3561 7241 6168 2025 4739 9501 5340 6446"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = {"6833 131 4151 1776 1959 7210 1903 6107 598 6220 94"
155c399d58 2012-12-08        kinaba: ,"24 5374 6718 2919 6068 6644 5070 710 7121 1630 370"
155c399d58 2012-12-08        kinaba: ,"3 1051 5739 9294 8798 3371 8107 2130 6608 534"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = {"7496 2412 2801 3473 5810 2714 7853 9714 5470 3558 "
155c399d58 2012-12-08        kinaba: ,"8143 2391 8234 7292 9311 1636 8978 1107 2262 9175 "
155c399d58 2012-12-08        kinaba: ,"7259 8842 5294 7209 2317 3825 3413 820 3774 5393"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = "NO";
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: CASE(5)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = {"219211 1996214 1706774 3634920 909831 1774128 8503"
155c399d58 2012-12-08        kinaba: ,"52 2233050 2099138 3380396 1128982 3682525 1483700"
155c399d58 2012-12-08        kinaba: ," 763080 487867 8203 1791027 463556 1103323 1406861"
155c399d58 2012-12-08        kinaba: ," 6374234 760949 4340236 727393 2073832 1289052 103"
155c399d58 2012-12-08        kinaba: ,"8147 4448130 151066 412440 1068735 377239 2677933 "
155c399d58 2012-12-08        kinaba: ,"1299598 339843 289973 3707319 555280 230418 431719"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = {"1638083 5698739 3105504 9726902 9745795 5049444 15"
155c399d58 2012-12-08        kinaba: ,"80592 3952120 6606668 7460527 7239299 8726128 4913"
155c399d58 2012-12-08        kinaba: ,"547 6264100 5701660 8865937 4969114 8014845 327236"
155c399d58 2012-12-08        kinaba: ,"1 6389154 9739755 2561669 9412417 5452337 3150506 "
155c399d58 2012-12-08        kinaba: ,"5832197 1571976 8779325 3306446 948271 5133709 949"
155c399d58 2012-12-08        kinaba: ,"394 6919798 7525636 3568024 6833196 9237472 733313"
155c399d58 2012-12-08        kinaba: ,"1 9939064 9720014"};
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = {"5860334 8007503 7455523 4864927 9573526 2718360 81"
155c399d58 2012-12-08        kinaba: ,"12104 6684287 9921506 4840886 5415948 3451454 5320"
155c399d58 2012-12-08        kinaba: ,"996 9268757 9261724 8254668 2292750 8035828 233352"
155c399d58 2012-12-08        kinaba: ,"1 7676906 5234406 8533320 6562751 4884098 4971897 "
155c399d58 2012-12-08        kinaba: ,"5569360 8519168 3100295 9351613 7733878 7579030 32"
155c399d58 2012-12-08        kinaba: ,"46775 7297460 8370542 7099759 5782969 2978083 3390"
155c399d58 2012-12-08        kinaba: ,"488 7482758 1332401 6094629 9717305 5503121 572842"
155c399d58 2012-12-08        kinaba: ,"1 4903563 6331656 2867455 3410007 7751527 7228221 "
155c399d58 2012-12-08        kinaba: ,"4111694 5171296 6847697 4601273 7599828 5515929 94"
155c399d58 2012-12-08        kinaba: ,"60593 9332762 5389080 4512091 8668538 5711743 5838"
155c399d58 2012-12-08        kinaba: ,"534 4825079 8145628 3810005 2964724 5594550 785748"
155c399d58 2012-12-08        kinaba: ,"3 6283769"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = {"5911694 8009943 212555 5838688 9896256 607434 5857"
155c399d58 2012-12-08        kinaba: ,"663 4616750 1477573 7168026 3090917 4379806 326465"
155c399d58 2012-12-08        kinaba: ,"7 4189076 2104028 3279691 94211 8503556 78457 4394"
155c399d58 2012-12-08        kinaba: ,"360 3344176 3223317 2624498 4883494 1532240 732937"
155c399d58 2012-12-08        kinaba: ,"1 1518674 1353567 892134 5536454 8527392 2603965 6"
155c399d58 2012-12-08        kinaba: ,"623264 8830827 2030444 3002706 83058 4475866 20876"
155c399d58 2012-12-08        kinaba: ,"25 1790695 4034441 5409379 3571098 4600050 736561 "
155c399d58 2012-12-08        kinaba: ,"250475 3733256 3011439 2144994 4523046 3119883 607"
155c399d58 2012-12-08        kinaba: ,"582 8361403 6525451 7518329 926803 4884524 8424659"
155c399d58 2012-12-08        kinaba: ," 7088689 5762049 9532481 4914186 7314621 4339084 3"
155c399d58 2012-12-08        kinaba: ,"741685 3837953 3177252 612550 9688871 5872931"};
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = "YES";
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: /*
155c399d58 2012-12-08        kinaba: CASE(6)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = ;
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: CASE(7)
155c399d58 2012-12-08        kinaba: 	string whiteX_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_));
155c399d58 2012-12-08        kinaba: 	string whiteY_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_));
155c399d58 2012-12-08        kinaba: 	string blackX_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_));
155c399d58 2012-12-08        kinaba: 	string blackY_[] = ;
155c399d58 2012-12-08        kinaba: 	  vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_));
155c399d58 2012-12-08        kinaba: 	string _ = ;
155c399d58 2012-12-08        kinaba: END
155c399d58 2012-12-08        kinaba: */
155c399d58 2012-12-08        kinaba: }
155c399d58 2012-12-08        kinaba: // END CUT HERE