fork download
copy 
  1. typedef complex<double> CMP;
  2.  
  3. class CheckerFreeness { public:
  4.     string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY)
  5. 	{
  6. 		stringstream swx(accumulate(whiteX.begin(), whiteX.end(), string("")));
  7. 		stringstream swy(accumulate(whiteY.begin(), whiteY.end(), string("")));
  8. 		stringstream sbx(accumulate(blackX.begin(), blackX.end(), string("")));
  9. 		stringstream sby(accumulate(blackY.begin(), blackY.end(), string("")));
  10.  
  11. 		vector<CMP> w;
  12. 		for(int x,y; (swx>>x)&&(swy>>y); )
  13. 			w.push_back(CMP(x,y));
  14.  
  15. 		vector<CMP> b;
  16. 		for(int x,y; (sbx>>x)&&(sby>>y); )
  17. 			b.push_back(CMP(x,y));
  18.  
  19. 		return has_checker(w,b) ? "NO" : "YES";
  20. 	}
  21.  
  22. 	bool has_checker(const vector<CMP>& w, const vector<CMP>& b)
  23. 	{
  24. 		for(int i=0; i<w.size(); ++i)
  25. 		for(int k=i+1; k<w.size(); ++k)
  26. 			if(has_crosser(w[i], w[k], b))
  27. 				return true;
  28. 		return false;
  29. 	}
  30.  
  31. 	bool has_crosser(CMP a, CMP b, const vector<CMP>& ps)
  32. 	{
  33. 		vector<double> arg_a, arg_b;
  34. 		vector<CMP> qs;
  35. 		for(int i=0; i<ps.size(); ++i)
  36. 		{
  37. 			double d = arg( (ps[i]-a)/(b-a) );
  38. 			if(d > 0) {
  39. 				arg_a.push_back(d);
  40. 				d = arg( (ps[i]-b)/(b-a) );
  41. 				arg_b.push_back(d);
  42. 			} else {
  43. 				qs.push_back(ps[i]);
  44. 			}
  45. 		}
  46. 		sort(arg_a.begin(), arg_a.end());
  47. 		sort(arg_b.begin(), arg_b.end());
  48. 		for(int i=0; i<qs.size(); ++i)
  49. 		{
  50. 			CMP q = qs[i];
  51. 			double aMax = arg((a-q) / (b-a));
  52. 			double bMax = arg((b-q) / (b-a));
  53. 			int aNum = lower_bound(arg_a.begin(), arg_a.end(), aMax) - arg_a.begin();
  54. 			int bNum = lower_bound(arg_b.begin(), arg_b.end(), bMax) - arg_b.begin();
  55. 			if(aNum != bNum)
  56. 				return true;
  57. 		}
  58. 		return false;
  59. 	}
  60. };
  61.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0rvTxw
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!