Pagini recente » Cod sursa (job #7896) | Cod sursa (job #901118) | Cod sursa (job #1166499) | Cod sursa (job #3263509) | Cod sursa (job #2552630)
#include<bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct coord
{
double x,y;
}sts[120001],v[120001],stdr[120001];
bool cmp(coord a, coord b)
{
if(a.y<b.y)
return true;
if(a.y==b.y&&a.x<b.x)
return true;
return false;
}
bool crb(coord p1,coord p2,coord p3)
{
if((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x)<=0)
return false;
return true;
}
int main()
{
int n,i,k,kk;
in>>n;
for(i=1;i<=n;i++)
{
in>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
k=2;
sts[1]=v[1];
sts[2]=v[2];
for(i=3;i<=n;i++)
{
while(k>=2&&crb(sts[k-1],sts[k],v[i])==false)
{
k--;
}
k++;
sts[k]=v[i];
}
stdr[1]=v[n];
stdr[2]=v[n-1];
kk=2;
for(i=n-2;i>=1;i--)
{
while(kk>=2&&crb(stdr[kk-1],stdr[kk],v[i])==false)
{
kk--;
}
kk++;
stdr[kk]=v[i];
}
out<<setprecision(6)<<fixed;
out<<kk+k-2<<'\n';
for(i=1;i<=k;i++)
{
out<<sts[i].x<<" "<<sts[i].y<<'\n';
}
for(i=2;i<kk;i++)
out<<stdr[i].x<<" "<<stdr[i].y<<'\n';
}