Pagini recente » Cod sursa (job #411383) | Cod sursa (job #1318421) | Cod sursa (job #2944652) | Cod sursa (job #433792) | Cod sursa (job #2205901)
#include <bits/stdc++.h>
using namespace std;
int n,s = 1, k = 2;
struct point{
double x, y;
} p[120010], ans[120010];
bool det(point a, point b, point c){
return (a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - a.y*b.x > 0);
}
bool cmp(point a, point b){
return det(p[1], a, b);
}
int main(){
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
cin >> n;
for (int i=1; i<=n; i++){
cin >> p[i].x >> p[i].y;
if (p[i].x < p[s].x || (p[i].x == p[s].x && p[i].y < p[s].y)) s = i;
}
swap (p[1], p[s]);
sort (p+2, p+1+n, cmp);
ans[1] = p[1]; ans[2] = p[2];
for (int i=3; i<=n; i++){
while (!det(ans[k-1], ans[k], p[i])) k--;
ans[++k] = p[i];
}
cout << k << "\n" << fixed << setprecision(12);
for (int i=1; i<=k; i++) cout << ans[i].x << " " << ans[i].y << "\n";
return 0;
}