Pagini recente » Cod sursa (job #1361969) | Cod sursa (job #2530408) | Cod sursa (job #778233) | Cod sursa (job #2531150) | Cod sursa (job #2523297)
#include <bits/stdc++.h>
#define x first
#define y second
#define DIM 120010
#define inf 1000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,j,pmin,k;
pair<double,double> v[DIM],s[DIM];
double det(const pair<double,double> &a,const pair<double,double> &b,const pair<double,double> &c) {
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(const pair<double,double> &a, const pair<double,double> &b) {
return det(v[1],a,b)>0.0;
}
int main() {
fin>>n;
v[0].x=v[0].y=inf;
for (i=1;i<=n;i++) {
fin>>v[i].x>>v[i].y;
if (v[i]<v[pmin])
pmin=i;
}
v[0]=v[pmin];
sort(v+2,v+n+1,cmp);
for (j=3;j<=n;j++)
if (det(v[1],v[2],v[j])!=0.0)
break;
i=2, j--;
while (i<j)
swap(v[i++],v[j--]);
s[1]=v[1], s[2]=v[2];
k=2;
for (i=3;i<=n;i++) {
while (k>=2&&det(s[k-1],s[k],v[i])<=0.0)
k--;
s[++k]=v[i];
}
fout<<k<<"\n";
for (i=1;i<=k;i++)
fout<<fixed<<setprecision(6)<<(int)1000000*s[i].x/1000000.0<<" "<<(int)1000000*s[i].y/1000000.0<<"\n";
return 0;
}