Pagini recente » Cod sursa (job #1927585) | Cod sursa (job #2308870) | Cod sursa (job #1832508) | Cod sursa (job #1350957) | Cod sursa (job #965212)
Cod sursa(job #965212)
#include <cstdio>
#include <algorithm>
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
using namespace std;
int n,vf;
struct point{double i,j;}p[100000],stak[100000];
void push(point p){stak[++vf]=p;}
void pop(){stak[vf].i=0;stak[vf--].j=0;}
struct cmp
{
bool operator ()(const point p1,const point p2)const
{
if(p1.i<p2.i)return 1;
if(p1.i==p2.i && p1.j<p2.j)return 1;
return 0;
}
};
void readdata()
{
fscanf(f,"%d",&n);
for(int i=1;i<=n;++i)
fscanf(f,"%lf%lf",&p[i].i,&p[i].j);
sort(p+1,p+n+1,cmp());
}
double linie(point d1,point d2,point P)//verificam daca punctul P este deasupra sau sub dreapta d1d2
{
return (((d1.i*d2.j) + (P.i*d1.j) + (d2.i*P.j))-((d1.i *P.j )+(d2.i * d1.j)+(P.i * d2.j)));
}
void solveHULL()
{
point pmin=p[1],pmax=p[n];
push(pmin);int i=2;//bagam in stiva primul pct
while(i<n && linie(pmin,pmax,p[i])<0)++i;push(p[i]);// bag in stiva si al 2 lea punct daca exista
++i;
while(i<=n)
{
if(linie(pmin,pmax,p[i])>=0)
{
push(p[i]);
if(linie(stak[vf-2],stak[vf],stak[vf-1])<0)
{
pop();
pop();
}
else
++i;
}
else ++i;
}
i-=2;
while(i>=1)
{
if(linie(pmin,pmax,p[i])<=0)
{
push(p[i]);
if(linie(stak[vf-2],stak[vf],stak[vf-1])<0)
{
pop();
pop();
}
else
--i;
}
else --i;
}
pop();
}
void print()
{
fprintf(g,"%d\n",vf);
while(vf)
{
fprintf(g,"%lf %lf\n",stak[vf].i,stak[vf].j);
pop();
}
}
int main()
{
readdata();
solveHULL();
print();
return 0;
}