Pagini recente » Cod sursa (job #2106124) | Cod sursa (job #569729) | Cod sursa (job #2531424) | Cod sursa (job #2004665) | Cod sursa (job #2150545)
#include <bits/stdc++.h>
using namespace std;
struct point{
long double x, y;
} P[120010], sol[120010];
int n, s = 1, k = 2;
bool crossproduct(point a, point b, point c){
return (a.y - c.y)*(a.x - b.x) < (a.y - b.y)*(a.x - c.x);
}
bool cmp(point a, point b){
return !crossproduct(a, b, P[1]);
}
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);
sol[1] = P[1];
sol[2] = P[2];
for (int i=3; i<=n; i++){
while (k >= 2 && crossproduct(sol[k-1], sol[k], P[i])) k--;
sol[++k] = P[i];
}
cout << k << "\n";
for (int i=1; i<=k; i++) cout << fixed << setprecision(12) << sol[i].x << " " << sol[i].y << "\n";
return 0;
}