fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7. FILE *in = fopen("new","r");
  8.  
  9.  
  10. struct point{ll s;ll e;};
  11.  
  12. bool comp(point a,point b)
  13. {
  14. 	if(a.s>b.s)
  15. 		return false;
  16. 	return true;
  17. }
  18. ll max1;
  19. void to_cover(vector<point> a,ll s,ll e,int f_i,int &count)
  20. {
  21. 	while(1)
  22. 	{
  23. 	int j;
  24. 	for(j=f_i;j<a.size();j++)
  25. 		if(a[j].s>s)
  26. 			break;
  27. 	if(j-f_i==0)
  28. 	{
  29. 		count=-1;
  30. 		return;
  31. 	}
  32. 	max1=LONG_MIN;
  33. 	//int max_i;
  34. 	for(int i=f_i;i<j;i++)
  35. 	{
  36. 		if(a[i].e>max1)
  37. 		{
  38. 			max1=a[i].e;
  39. 		//	max_i=i;
  40. 		}
  41. 	}
  42. 	//cout << a[max_i].s << "\t" << a[max_i].e << endl;
  43. 	count++;
  44. 	if(max1>=e)
  45. 		return;
  46. 	s=max1;f_i=j;	
  47. 	}
  48. }
  49.  
  50. int main()
  51. {
  52. 	ios::sync_with_stdio(false);
  53. 	int t;
  54. 	cin >> t;
  55. 	while(t--)
  56. 	{
  57. 	ll n,k,m;
  58. 	cin >> n >> k >> m;
  59. 	ll s=(n-k)/2 + 1;
  60. 	ll e = s+k;
  61. 	vector<point> ax;
  62. 	vector<point> ay;
  63. 	for(int i=0;i<m;i++)
  64. 	{
  65. 		ll hx,hy;
  66. 		ll tx,ty;
  67. 		cin >> hx >> hy >> tx >> ty;
  68. 		if(hx==tx)
  69. 		{
  70. 			point p; 
  71. 			p.s=hy;p.e=ty;
  72. 			ay.push_back(p);
  73.  
  74. 		}
  75. 		if(hy==ty)
  76. 		{
  77. 			point p;
  78. 			p.s=hx;p.e=tx;
  79. 			ax.push_back(p);
  80. 		}
  81. 	}
  82.  
  83. 	sort(ax.begin(),ax.end(),comp);// sort by starting point
  84. 	sort(ay.begin(),ay.end(),comp);// sort by starting point
  85. 	int varx=0,vary=0;
  86. 	to_cover(ax,s,e,0,varx);// chooses the one segment whose starting point is valid and end point is longest for horizontal 
  87.  
  88. 	to_cover(ay,s,e,0,vary);//chooses the one segment whose starting point is valid and end point is longest for vertical
  89.  
  90. 	if(varx==-1 || vary==-1)
  91. 		cout <<  -1 << endl;
  92. 	else
  93. 		cout << varx+vary << endl;
  94. 	}
  95.     return 0;
  96. }
  97.  
  98.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
2
7 3 7
1 1 6 1
1 2 3 2
5 2 5 2
2 4 2 6
6 2 6 4
5 6 5 7
7 1 7 4
7 3 7
1 1 6 1
1 2 3 2
5 2 5 2
2 6 2 6
6 2 6 4
5 6 5 7
7 1 7 4
stdout
copy 
3
-1
https://ideone.com/gtN4CV
language:
C++ (gcc 8.3)
created:
6 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!