fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. typedef struct point
  7. {
  8. 	int y, x;	
  9. }POINT;
  10.  
  11. POINT points[100001];
  12.  
  13. inline double ccw(const POINT &p1, const POINT &p2, const POINT &p3)
  14. {
  15. 	return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
  16. }
  17.  
  18. inline bool cmp(const POINT &p, const POINT &q) 
  19. {
  20. 	if( p.y < q.y ) return true;
  21. 	else if( p.y == q.y )
  22. 	{
  23. 		if( p.x <= q.x ) return true;
  24. 		else return false;
  25. 	}
  26. 	else return false;
  27. }
  28.  
  29. inline bool cmpAngle(const POINT &p, const POINT &q) 
  30. {
  31. 	if( ccw(points[1], p, q) > 0 ) return true;
  32. 	else return false;
  33. }
  34.  
  35. int main()
  36. {
  37. 	int N, ans = 1;
  38.  
  39. 	scanf("%d", &N);
  40.  
  41. 	for(int i=1; i<=N; ++i)
  42. 		scanf("%d %d", &points[i].x, &points[i].y);
  43.  
  44. 	sort(points+1, points+N+1, cmp);
  45. 	sort(points+2, points+N+1, cmpAngle);
  46.  
  47. 	points[0] = points[N];
  48.  
  49. 	for(int i=2; i<=N; ++i)
  50. 	{
  51. 		while( ccw(points[ans-1], points[ans], points[i]) <= 0 )
  52. 			if( ans > 1 )
  53. 			{
  54. 				--ans;
  55. 				continue;
  56. 			}
  57. 			else if( i == N )
  58. 				break;
  59. 			else 
  60. 				++i;
  61. 		++ans;
  62. 		swap(points[ans], points[i]);
  63. 	}
  64.  
  65. 	for(int i=1;i<=M;++i)
  66. 		printf("%d %d\n", points[i].x, points[i].y);
  67.  
  68. 	printf("%d", ans);
  69.  
  70. 	return 0;	
  71. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:65:17: error: ‘M’ was not declared in this scope
  for(int i=1;i<=M;++i)
                 ^
stdout
copy 
Standard output is empty
https://ideone.com/ewwGZ4
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!