fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <stack>
  5. #include <functional>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. void main_func();
  10. bool sort_address(long int *,long int *);
  11. long int ccw(long int,long int,long int,long int,long int,long int );
  12.  
  13. int main()
  14. {
  15. 	long n;
  16. 	cin>>n;
  17. 	while(n>0)
  18. 	{
  19. 		main_func();
  20. 		n--;
  21. 	}
  22. }
  23.  
  24. void main_func()
  25. {
  26. 	long int vals,i;
  27. 	vector<long int> coords;
  28. 	vector<long int *> address;
  29. 	cin>>vals;
  30. 	i=0;
  31. 	while(i<vals)
  32. 	{
  33. 		long int temp;
  34. 		cin>>temp;
  35. 		coords.push_back(temp);
  36. 		i++;
  37. 	}
  38. 	i=0;
  39. 	while(i<vals)
  40. 	{
  41. 		address.push_back(&coords[i]);
  42. 		i++;
  43. 	}
  44. 	address.pop_back();
  45. 	sort(address.begin(),address.end(),sort_address);
  46. 	long int * itr,* end,prev;
  47. 	end=&coords[vals-1];
  48. 	i=0;
  49. 	vector<long int> pnt_coll;
  50. 	while(i < vals-1)
  51. 	{
  52. 		itr=address[i];
  53. 		if(i!=0)
  54. 		{
  55. 			if(prev == *itr)//removes the occurence of the same points
  56. 			{
  57. 				i++;
  58. 				continue;
  59. 			}
  60. 		}
  61. 		pnt_coll.push_back(*itr);
  62. 		prev=*itr;
  63. 		itr++;
  64. 		long int max=*itr;
  65. 		long int min=*itr;
  66. 		while(itr!=end)
  67. 		{
  68. 			itr++;
  69. 			if(*itr > max)
  70. 				max=*itr;
  71. 			if(*itr<min)
  72. 				min=*itr;
  73. 		}
  74. 		pnt_coll.push_back(min);
  75. 		pnt_coll.push_back(max);
  76. 		i++;
  77. 	}
  78. 	if(pnt_coll.size()<9)
  79. 	{
  80. 		if(pnt_coll[1]==pnt_coll[2] && pnt_coll[4]==pnt_coll[5])
  81. 		{
  82. 			cout<<0<<endl;
  83. 			return;
  84. 		}
  85. 	}
  86.  
  87. 	long int pivot_x=pnt_coll[0],pivot_y=pnt_coll[1],
  88. 			 final_x=pnt_coll[0],final_y=pnt_coll[2],
  89. 			 final2_x=pnt_coll[0],final2_y=pnt_coll[1];
  90. 	i=1;
  91. 	long int tot=pnt_coll.size()/3,area=0;
  92. 	while(i<tot-1)
  93. 	{
  94. 		int flag,flag2;
  95. 		flag=1;
  96. 		flag2=1;
  97. 		for(int j=i+1;j<tot;j++)
  98. 		{
  99. 			if(ccw(final_x,final_y,pnt_coll[3*i],pnt_coll[3*i+2],pnt_coll[3*j],pnt_coll[3*j+2])<=0)
  100. 			{
  101. 				flag=0;
  102. 			}
  103. 			if(ccw(final2_x,final2_y,pnt_coll[3*i],pnt_coll[3*i+1],pnt_coll[3*j],pnt_coll[3*j+1])>=0)
  104. 			{
  105. 				flag2=0;
  106. 				break;
  107. 			}
  108. 			if(!(flag+flag2))
  109. 				break;
  110. 		}
  111. 		if(flag)
  112. 		{
  113. 			area+=ccw(pivot_x,pivot_y,final_x,final_y,pnt_coll[3*i],pnt_coll[3*i+2]);//CCW
  114. 			final_x=pnt_coll[3*i];
  115. 			final_y=pnt_coll[3*i+2];
  116. 		}
  117. 		if(flag2)
  118. 		{
  119. 			area-=ccw(pivot_x,pivot_y,final2_x,final2_y,pnt_coll[3*i-3],pnt_coll[3*i-2]);//CCW
  120. 			final2_x=pnt_coll[3*i];
  121. 			final2_y=pnt_coll[3*i+1];
  122. 		}
  123. 		i++;
  124. 	}
  125. 	area+=ccw(pivot_x,pivot_y,final_x,final_y,pnt_coll[3*i],pnt_coll[3*i+2]);
  126. 	//cout<<area<<"......\n";
  127. 	area-=ccw(pivot_x,pivot_y,final2_x,final2_y,pnt_coll[3*i],pnt_coll[3*i+1]);
  128. 	if(pnt_coll[3*i+2]-pnt_coll[3*i+1])
  129. 		area+=(pnt_coll[3*i]-pivot_x)*(pnt_coll[3*i+2]-pnt_coll[3*i+1]);
  130. 	cout<<area<<endl;
  131. }
  132.  
  133. bool sort_address(long int *a,long int *b)
  134. {
  135. 	return *a < *b;
  136. }
  137.  
  138. long int ccw(long int x1,long int y1,long int a,long int b,long int x2,long int y2)
  139. {
  140. 	return (a-x1)*(b-y2)-(b-y1)*(a-x2);
  141. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
2
3
2 4 1
4
2 4 1 3
stdout
copy 
6
13
https://ideone.com/EoLmgU
language:
C++14 (gcc 8.3)
created:
9 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!