Pagini recente » Cod sursa (job #1271017) | Cod sursa (job #2715190) | Cod sursa (job #981304) | Cod sursa (job #15722) | Cod sursa (job #2474995)
#include<bits/stdc++.h>
#define N 121010
#define x first
#define y second
using namespace std;
typedef pair<double,double> point;
int n,mn;
point a[N], O;
int det(point A, point B, point 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(point l, point r) {
return (det(a[1], l,r)>0);
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n; mn=1;
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+2,a+1+n, cmp);
int l=2;
for (int i=3; i<=n; i++) {
while (l>=2 && det(a[l-1], a[l], a[i])<0) l--;
a[++l] = a[i];
}
cout<<l<<'\n';
for (int i=1; i<=l; i++) {
cout<<fixed<<setprecision(12)<<a[i].x<<" "<<a[i].y<<'\n';
}
return 0;
}