Pagini recente » Istoria paginii runda/becreative24/clasament | Cod sursa (job #704345) | Cod sursa (job #2407937) | Cod sursa (job #1423818) | Cod sursa (job #2392376)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point{
long double x,y;
};
const long double INF = 1000000003;
const int NMax = 120005;
point a[NMax];
int n,top,ind;
int st[NMax];
long double unghi(point A, point B, point C){
return (A.y - B.y) * (A.x - C.x) - (A.y - C.y) * (A.x - B.x);
}
bool cmp(point x, point y){
return unghi(a[1], x, y) > 0;
}
int main(){
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
int mn_x = INF, mn_y = INF;
for(int i = 1; i <= n; ++i){
cin >> a[i].x >> a[i].y;
if(a[i].x == mn_x){
if(a[i].y < mn_y){
mn_x = a[i].x;
mn_y = a[i].y;
ind = i;
}
}
if(a[i].x < mn_x){
mn_x = a[i].x;
mn_y = a[i].y;
ind = i;
}
}
swap(a[1], a[ind]);
sort(a + 2, a + 1 + n, cmp);
st[++top] = 1;
st[++top] = 2;
for(int i = 3; i <= n; ++i){
while(unghi(a[st[top - 1]], a[st[top]], a[i]) < 0){
top--;
}
st[++top] = i;
}
cout << top << '\n';
for(int i = top; i >= 1; --i){
cout << fixed << setprecision(12) << a[st[i]].x << ' ' << a[st[i]].y << '\n';
}
return 0;
}