Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("infasuratoare.in");
- ofstream fout("infasuratoare.out");
- struct point
- {
- double x, y;
- };
- const int NMAX = 120005;
- int n;
- int idx[NMAX];
- point arr[NMAX];
- inline double det(point a, point b, point c)
- {
- return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y);
- }
- inline bool Trig(const point &a, const point &b)
- {
- return det(arr[1], a, b) > 0;
- }
- int main()
- {
- fin >> n;
- for(int i = 1; i <= n; ++ i)
- fin >> arr[i].x >> arr[i].y;
- int minY = arr[1].y, minpos = 1;
- for(int i = 1; i <= n; ++ i)
- {
- if(minY > arr[i].y)
- {
- minpos = i;
- minY = arr[i].y;
- }
- }
- swap(arr[1], arr[minpos]);
- sort(arr + 2, arr + n + 1, Trig);
- idx[1] = 1;
- idx[2] = 2;
- int k = 2;
- for(int i = 3; i <= n; ++i)
- {
- while(k > 1 && det(arr[idx[k-1]], arr[idx[k]], arr[i]) <= 0)
- k--;
- idx[++k] = i;
- }
- fout << k << '\n';
- for(int i = 1; i <= k; ++ i)
- fout << fixed << setprecision(12) << arr[idx[i]].x << ' ' << arr[idx[i]].y << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement