Pagini recente » Cod sursa (job #2489210) | Cod sursa (job #1575684) | Cod sursa (job #95302) | Cod sursa (job #2177743) | Cod sursa (job #964640)
Cod sursa(job #964640)
#include<algorithm>
#include<stack>
#include<cstdio>
using namespace std;
struct pct {double x,y;} a[120001],st[120001];
int n,vf=-1;
struct cmp{
bool operator ()(const pct p1,const pct p2)const
{
if(p1.x<p2.x)return 1;
if(p1.x==p2.x&&p1.y<p2.y)return 1;
return 0;
}
};
int parte(pct a,pct b,pct m)
{
return a.x*b.y+b.x*m.y+m.x*a.y-m.y*a.x-a.y*b.x-m.x*b.y;
}
int main()
{
FILE *f=fopen("infasuratoare.in","r");
int i;
fscanf(f,"%d",&n);
for(i=0;i<n;i++)
fscanf(f,"%lf%lf",&a[i].x,&a[i].y);
sort(a,a+n,cmp());
st[++vf]=a[0];
i=1;
while(i+1<n && parte(a[0],a[n-1],a[i])<0)i++;
if(i+1<n)st[++vf]=a[i];
i++;
while(i+1<n)
if(parte(a[0],a[n-1],a[i])>0)//deci a[i] e din jumatatea de sus
{
st[++vf]=a[i];
if(parte(st[vf-2],st[vf],st[vf-1])>0)i++;
else
if(vf>1)vf-=2;
}
else i++;
st[++vf]=a[n-1];
i=n-2;
while(i>0)
if(parte(a[0],a[n-1],a[i])<0)
{
st[++vf]=a[i];
if(parte(st[vf-2],st[vf],st[vf-1])>0)i--;
else
if(vf>1)vf-=2;
}
else i--;
f=fopen("infasuratoare.out","w");
fprintf(f,"%d\n",vf+1);
while(vf+1)
{
fprintf(f,"%lf %lf\n",st[vf].x,st[vf].y);
vf--;
}
return 0;
}