Pagini recente » Cod sursa (job #1575792) | Cod sursa (job #2755868) | Cod sursa (job #1246138) | Cod sursa (job #2752839) | Cod sursa (job #2284451)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point {
double x, y;
};
point a[120003];
bool sel[120003];
int st[120003];
int N, k, pas;
bool cmp(point a, point b) {
if(a.x < b.x) return true;
else if(a.x == b.x && a.y <= b.y) return true;
return false;
}
int determ(point a, point b, point c) {
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
int main()
{
f >> N;
for(int i = 1; i <= N; i++) {
f >> a[i].x >> a[i].y;
}
sort(a + 1, a + N + 1, cmp);
st[++k] = 1;
st[++k] = 2;
sel[2] = true;
pas = 1;
for(int i = 3; i <= N; i++) {
while(k > 1 && determ(a[st[k- 1]], a[st[k]], a[i]) >= 0) {
sel[st[k]] = false;
st[k--] = 0;
}
st[++k] = i;
sel[i] = true;
}
for(int i = N; i >= 1; i--) {
if(!sel[i]) {
while(k > 1 && determ(a[st[k- 1]], a[st[k]], a[i]) >= 0) {
sel[st[k]] = false;
st[k--] = 0;
}
st[++k] = i;
sel[i] = true;
}
}
g << k - 1 << setprecision(6) << fixed << "\n";
for(int i = k - 1; i >= 1; i--) {
g << a[st[i]].x << " " << a[st[i]].y << "\n";
}
return 0;
}