Pagini recente » Cod sursa (job #97405) | Cod sursa (job #1454059) | Cod sursa (job #2879945) | Cod sursa (job #1505338) | Cod sursa (job #1267497)
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
};
int compare (const void * a, const void * b)
{
if ( (*(punct*)a).x < (*(punct*)b).x ) return -1;
if ( (*(punct*)a).x == (*(punct*)b).x && (*(punct*)a).y < (*(punct*)b).y ) return -1;
if ( (*(punct*)a).x > (*(punct*)b).x ) return +1;
if ( (*(punct*)a).x == (*(punct*)b).x && (*(punct*)a).y > (*(punct*)b).y ) return +1;
return 0;
}
int unghi(punct A, punct B, punct C)
{
double p,q;
p=A.x*B.y+B.x*C.y+C.x*A.y;
q=C.x*B.y+A.x*C.y+B.x*A.y;
if(p<q)return -1;
if(p>q)return +1;
return 0;
}
int N, nup, ndown, i;
punct V[120005],Up[120005], Down[120005];
int main()
{
fin>>N;
for(i=1;i<=N;i++)
{
fin>>V[i].x>>V[i].y;
}
qsort(V+1,N,sizeof(punct),compare);
/*
for(i=1;i<=N;i++)
{
fout<<V[i].x<<" "<<V[i].y<<'\n';
}
fout<<'\n';
*/
Up[1]=V[1];
nup=1;
for(i=2;i<=N-1;i++)
{
if(unghi(V[1],V[i],V[N])<=0)
{
while(nup>=2 && unghi(Up[nup-1],Up[nup],V[i])>0)
{
nup--;
}
nup++;
Up[nup]=V[i];
}
}
/*
for(i=1;i<=nup;i++)
{
fout<<Up[i].x<<" "<<Up[i].y<<'\n';
}
fout<<'\n';
*/
Down[1]=V[1];
ndown=1;
for(i=2;i<=N;i++)
{
if(unghi(V[1],V[i],V[N])>=0)
{
while(ndown>=2 && unghi(Down[ndown-1],Down[ndown],V[i])<0)
{
ndown--;
}
ndown++;
Down[ndown]=V[i];
}
}
/*
for(i=1;i<=ndown;i++)
{
fout<<Down[i].x<<" "<<Down[i].y<<'\n';
}
fout<<'\n';
*/
fout<<ndown+nup-1<<'\n';
for(i=1;i<=ndown;i++)
{
fout<<Down[i].x<<" "<<Down[i].y<<'\n';
}
for(i=nup;i>=2;i--)
{
fout<<Up[i].x<<" "<<Up[i].y<<'\n';
}
fout.close();
fin.close();
return 0;
}