Pagini recente » Cod sursa (job #915477) | Cod sursa (job #2781827) | Cod sursa (job #701342) | Cod sursa (job #697453) | Cod sursa (job #2121059)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point{
double x, y;
};
int N, vf;
point a[120100], st[120100];
double det(point a, point b, point c){
return (a.x * b.y + b.x * c.y + a.y * c.x - c.x * b.y - b.x * a.y - a.x * c.y);
}
bool cmp(point a, point b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool cmp2(point b, point c){
return det(a[1], b, c) < 0;
}
int main(){
in >> N;
for(int i = 1; i <= N; i++)
in >> a[i].x >> a[i].y;
sort(a + 1, a + N + 1, cmp);
sort(a + 2, a + N + 1, cmp2);
st[1] = a[1];
st[2] = a[2];
vf = 2;
for(int i = 3; i <= N; i++){
while(vf >= 2 && det(st[vf - 1], st[vf], a[i]) > 0)
vf--;
st[++vf] = a[i];
}
out << vf << '\n';
out << fixed << setprecision(6);
for(int i = 1; i <= vf; i++)
out << st[i].x << ' ' << st[i].y << '\n';
return 0;
}