Pagini recente » Cod sursa (job #783419) | Cod sursa (job #214916) | Cod sursa (job #1696846) | Cod sursa (job #1940179) | Cod sursa (job #407344)
Cod sursa(job #407344)
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define nn 120005
struct puncte{
double x,y;
};
puncte v[nn];
int z[nn],n,m;
double directie(int a,int b,int c)
{
return ((v[b].x-v[a].x)*(v[c].y-v[a].y)-(v[b].y-v[a].y)*(v[c].x-v[a].x));
}
double functie(puncte a,puncte b)
{
return (double)(a.x - v[1].x) * (b.y - v[1].y) > (double)(b.x - v[1].x) * (a.y - v[1].y);
}
int dir(puncte A,puncte B,puncte C)
{
double det=A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
if(det==0)
return 0;
if(det<0)
return -1;
return 1;
}
int polare(puncte A,puncte B)
{
if(dir(v[1],A,B)>0)
return 1;
if(dir(v[1],A,B)<0)
return 0;
return(v[1].x-A.x)*(v[1].x-A.x)+(v[1].y-A.y)*(v[1].y-A.y) <
(v[1].x-B.x)*(v[1].x-B.x)+(v[1].y-B.y)*(v[1].y-B.y);
}
void infasor(int pmin)
{
sort(v+2,v+n,polare);
z[++m]=pmin;
int gata=0;
for(int i=2;i<n;++i)
{
while(directie(z[m-1],z[m],i)<=0 && m>1)
--m;
z[++m]=i;
}
}
int main()
{
ifstream fin("infasuratoare.in");
fin>>n;
for(int i=1;i<=n;++i)
fin>>v[i].x>>v[i].y;
int pmin=1;
for(int i=2;i<=n;++i)
if(v[i].y<v[pmin].y)
pmin=i;
else if(v[i].x==v[pmin].x)
if(v[i].x<v[pmin].x)
pmin=i;
puncte aux=v[pmin];
v[pmin]=v[1];
v[1]=aux;
infasor(pmin);
FILE *f=fopen("infasuratoare.out","w");
//ofstream fout("infasuratoare.out");
fprintf(f,"%d\n",m);
//fout<<m-1<<"\n";
for(int i=1;i<=m;++i)
//fout<<v[z[i]].x<<" "<<v[z[i]].y<<"\n";
fprintf(f,"%f %f\n",v[z[i]].x,v[z[i]].y);
return 0;
}