Pagini recente » Cod sursa (job #1833091) | Cod sursa (job #2094128) | Cod sursa (job #723894) | Cod sursa (job #1737625) | Cod sursa (job #2575981)
#include <bits/stdc++.h>
#define inf INT_MAX
#define DIM 120010
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,pmin,i,j,k;
pair<double,double> p[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) {
double d=det(p[1],a,b);
if (d!=0)
return d>0;
return (a.x*a.x+a.y*a.y)>(b.x*b.x+b.y*b.y);
}
int main() {
fin>>n;
p[0]={inf,inf};
for (i=1;i<=n;i++) {
fin>>p[i].x>>p[i].y;
if (p[i].y<p[pmin].y||(p[i].y==p[pmin].y&&p[i].x<p[pmin].x))
pmin=i;
}
p[0]=p[pmin];
swap(p[1],p[pmin]);
for (i=1;i<=n;i++) {
p[i].x-=p[0].x;
p[i].y-=p[0].y;
}
sort(p+2,p+n+1,cmp);
for (j=3;j<=n;j++) {
if (det(p[1],p[2],p[j]))
break;
}
i=2, j--;
while (i<j)
swap(p[i++],p[j--]);
s[1]=p[1], s[2]=p[2];
k=2;
for (i=3;i<=n;i++) {
while (k>=2&&det(s[k-1],s[k],p[i])<0)
k--;
s[++k]=p[i];
}
fout<<k<<"\n";
for (i=1;i<=k;i++)
fout<<fixed<<setprecision(6)<<(int)(s[i].x+p[0].x)*1000000/1000000.0<<" "<<(int)(s[i].y+p[0].y)*1000000/1000000.0<<"\n";
return 0;
}