Pagini recente » Cod sursa (job #2658242) | Borderou de evaluare (job #1791330) | Cod sursa (job #1576212) | Borderou de evaluare (job #486521) | Cod sursa (job #2195723)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point{
double x, y;
};
int n, vf;
point P[120100], st[120100];
double delta(point A, point B, point C){
return A.x * B.y + C.x * A.y + B.x * C.y - C.x * B.y - A.x * C.y - B.x * A.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 delta(P[1], B, C) < 0;
}
int main(){
in >> n;
for(int i = 1; i <= n; i++)
in >> P[i].x >> P[i].y;
sort(P + 1, P + n + 1, cmp);
st[1] = P[1];
sort(P + 2, P + n + 1, cmp2);
st[2] = P[2];
vf = 2;
for(int i = 3; i <= n; i++){
while(vf > 2 && delta(st[vf - 1], st[vf], P[i]) > 0)
vf--;
st[++vf] = P[i];
}
out << vf;
for(; vf; vf--)
out << fixed << setprecision(6) << '\n' << st[vf].x << ' ' << st[vf].y;
return 0;
}