Pagini recente » Cod sursa (job #3270277) | Cod sursa (job #2381399) | Cod sursa (job #765264) | Cod sursa (job #2367391) | Cod sursa (job #2474997)
#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], s[N],O;
double 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; s[1]=a[1], s[2]=a[2]; a[n+1]=a[1];
for (int i=3; i<=n+1; i++) {
while (l>=2 && det(s[l-1], s[l], a[i])<0) l--;
s[++l] = a[i];
}
cout<<l-1<<'\n';
for (int i=1; i<l; i++) {
cout<<fixed<<setprecision(12)<<s[i].x<<" "<<s[i].y<<'\n';
}
return 0;
}