Pagini recente » Cod sursa (job #1058330) | Cod sursa (job #1794386) | Cod sursa (job #516718) | Cod sursa (job #2933749) | Cod sursa (job #2316679)
#include<bits/stdc++.h>
#define pdd pair<double, double>
#define N 120010
#define x first
#define y second
using namespace std;
int n, mn;
pdd a[N];
pdd s[N];
int det(pdd A, pdd B, pdd C) {
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
bool cmp(pdd l, pdd r) {
return (det(a[1],l,r)>0);
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n; a[0] = {1e9+1,0};
for (int i=1; i<=n; ++i) {
cin>>a[i].x>>a[i].y;
if (a[i].x<a[mn].x || a[i].x==a[mn].x && a[i].y < a[mn].y) mn=i;
}
swap(a[1],a[mn]);
sort(a+1,a+1+n,cmp);
int last=2;
s[1]=a[1], s[2]=a[2];
for (int i=3; i<=n; ++i) {
while (last>=3 && det(s[last-1], s[last], a[i])<0) last--;
s[++last]=a[i];
}
cout<<last<<'\n';
for (int i=1; i<=last; ++i) cout<<fixed<<setprecision(12)<<s[i].x<<" "<<s[i].y<<'\n';
return 0;
}