Pagini recente » Cod sursa (job #2710055) | Cod sursa (job #2114586) | Cod sursa (job #3157032) | Cod sursa (job #2720978) | Cod sursa (job #2757826)
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
FILE*in=fopen("infasuratoare.in","r");
FILE*out=fopen("infasuratoare.out","w");
int n,i,it,itt;
const int cx=-1000000009;
const int cy=-1000000009;
struct pct
{
double x,y;
};
pct p[120003],s[120003],ss[120003];
bool sor(pct a,pct b)
{
return (b.y-cy)*(a.x-cx)>(a.y-cy)*(b.x-cx);
}
int main()
{
fscanf(in,"%d",&n);
for(i=1;i<=n;i++)
{
fscanf(in,"%lf %lf",&p[i].x,&p[i].y);
}
sort(p+1,p+n+1,sor);
s[1]=p[1];
it=1;
for(i=2;i<=n;i++)
{
while(it>=2&&(s[it].y-s[it-1].y)*(p[i].x-s[it].x)>(p[i].y-s[it].y)*(s[it].x-s[it-1].x))
{
it--;
}
it++;
s[it]=p[i];
}
ss[1]=p[n];
itt=1;
for(i=n-1;i>=1;i--)
{
while(itt>=2&&(ss[itt].y-ss[itt-1].y)*(p[i].x-ss[itt].x)>(p[i].y-ss[itt].y)*(ss[itt].x-ss[itt-1].x))
{
itt--;
}
itt++;
ss[itt]=p[i];
}
fprintf(out,"%d\n",it+itt-2);
for(i=1;i<=it;i++)
{
fprintf(out,"%.12f %.12f\n",s[i].x,s[i].y);
}
for(i=2;i<itt;i++)
{
fprintf(out,"%.12f %.12f\n",ss[i].x,ss[i].y);
}
}