Pagini recente » Cod sursa (job #2316787) | Cod sursa (job #1683562) | Cod sursa (job #56265) | Cod sursa (job #1283190) | Cod sursa (job #2183431)
#include<bits/stdc++.h>
#define x first
#define y second
#define NMAX 120100
using namespace std;
typedef pair<double,double> pii;
pii a[NMAX];
int s[NMAX];
int mn,n;
double crossProduct(pii O, pii L, pii R) {
return (L.x-O.x)*(R.y-O.y)-(L.y-O.y)*(R.x-O.x);
}
bool cmp(pii l, pii r) {
return crossProduct(a[1],l,r)>0;
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
a[0].x=a[0].y=1e9;
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[mn],a[1]);
sort(a+2,a+1+n,cmp);
s[1]=1; s[2]=2; int i=3; int p=3; int last=2;
for (int i=3; i<=n; i++) {
while (last>=3 && crossProduct(a[s[last]],a[i],a[s[last-1]])<0) last--;
s[++last]=i;
}
cout<<last<<'\n';
for (int i=1; i<=last; i++) {
cout<<fixed<<setprecision(10)<<a[s[i]].x<<" "<<a[s[i]].y<<'\n';
}
return 0;
}