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 16024KB
stdin
8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
stdout
1 1
3 1
2 1
3 2
2 2
2 3
1 3
1 2
6