Pagini recente » Cod sursa (job #1983881) | Cod sursa (job #2947821) | Cod sursa (job #2937372) | Cod sursa (job #400046) | Cod sursa (job #2391437)
#include <bits/stdc++.h>
using namespace std;
#define N 120005
#define eps 0.000001
struct point{
double x, y;
} a[N], p[N];
int n, s = 1;
// 1 - la stanga, 0 - la dreapta
bool det(point a, point b, point c){
double rs = a.x * b.y + b.x * c.y + c.x * a.y;
rs -= (b.y * c.x + c.y*a.x + a.y * b.x);
return (rs > eps);
}
bool cmp (point unu, point doi){
return det(a[1], unu, doi);
}
int main(){
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
cin >> n;
for (int i=1; i<=n; i++){
cin >> a[i].x >> a[i].y;
if (a[i].x < a[s].x || (a[i].x == a[s].x && a[i].y < a[s].y)) s = i;
}
swap(a[1], a[s]);
sort(a+2, a+1+n, cmp);
p[1] = a[1]; p[2] = a[2]; p[3] = a[3]; s = 3;
for (int i=4; i<=n; i++){
while (s > 2 && !det(p[s-1], p[s], a[i])) s--;
p[++s] = a[i];
}
cout << s << '\n';
cout << fixed << setprecision(6);
for (int i=1; i<=s; i++) cout << p[i].x << ' ' << p[i].y << '\n';
return 0;
}