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. 	for(int i=1;i<=N;++i)
  48. 		printf("%d %d\n", points[i].x, points[i].y);
  49.  
  50. 	points[0] = points[N];
  51.  
  52. 	for(int i=2; i<=N; ++i)
  53. 	{
  54. 		while( ccw(points[ans-1], points[ans], points[i]) <= 0 )
  55. 			if( ans > 1 )
  56. 			{
  57. 				--ans;
  58. 				continue;
  59. 			}
  60. 			else if( i == N )
  61. 				break;
  62. 			else 
  63. 				++i;
  64. 		++ans;
  65. 		swap(points[ans], points[i]);
  66. 	}
  67.  
  68. 	printf("%d", ans);
  69.  
  70. 	return 0;	
  71. }
Success #stdin #stdout 0s 16848KB
comments (?)
stdin
copy 
8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
stdout
copy 
1 1
2 1
3 1
3 2
2 2
2 3
1 2
1 3
5
https://ideone.com/SVYTtQ
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!