Pagini recente » Cod sursa (job #1544787) | Cod sursa (job #2035993) | Cod sursa (job #2169602) | Cod sursa (job #1724142) | Cod sursa (job #1802790)
#include<bits/stdc++.h>
using namespace std;
struct point {
double x, y;
bool operator < (point &b) {
if(x == b.x) return y < b.y;
return x < b.x;
}
};
int i, n;
point a[120005];
vector<point> up, down, ans;
double area(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 * b.y; }
bool cw(point a, point b, point c) { return area(a, b, c) < 0; }
bool ccw(point a, point b, point c) {return area(a, b, c) > 0; }
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
ios_base::sync_with_stdio(0);
cin >> n;
for(i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
up.push_back(a[1]); down.push_back(a[1]);
for(i = 2; i <= n; ++i) {
if(i == n || cw(a[1], a[i], a[n])) {
while(up.size() > 1 && !cw(up[up.size() - 2], up[up.size() - 1], a[i])) up.pop_back();
up.push_back(a[i]);
}
if(i == n || ccw(a[1], a[i], a[n])) {
while(down.size() > 1 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i])) down.pop_back();
down.push_back(a[i]);
}
}
down.pop_back();
reverse(down.begin(), down.end());
down.pop_back();
for(auto it : down) up.push_back(it);
cout << up.size() << '\n';
for(auto it : up) cout << setprecision(8) << fixed << it.x << ' ' << it.y << '\n';
return 0;
}