Pagini recente » Cod sursa (job #2152405) | Cod sursa (job #1398220) | Cod sursa (job #2817902) | Cod sursa (job #3234000) | Cod sursa (job #747282)
Cod sursa(job #747282)
#include<fstream>
#include<algorithm>
#define nmax 120010
#define inf INT_MAX
#include<iomanip>
using namespace std;
struct punct {double x,y,p;};
// x coordonata de pe axa Ox a punctului
// y coordonata de pe axa Oy a punctului
// p panta dreptei determinata de punct si punctul de extrema
punct p[nmax],alfa;
//alfa va fi punctul de extrema, iar in vectorul p[] voi retine toate punctele din plan
int sol[nmax],n;
// in vectorul sol[] retin indicele punctelor ce se afla pe infasuratoare
void citire()
{
int i;
ifstream in("infasuratoare.in");
in>>n;
for (i=1;i<=n;i++)
in>>p[i].x>>p[i].y;
}
void cauta_extrema()
{
//functie ce gfaseste punctul de extrema stanga, jos
int i,poz;
punct aux;
alfa.x=alfa.y=1000000001;
for (i=1;i<=n;i++)
{
if (p[i].x<alfa.x)
{
alfa=p[i];
poz=i;
}
else if (p[i].x==alfa.x&&p[i].y<alfa.y)
{
alfa=p[i];
poz=i;
}
}
aux=p[poz];
p[poz]=p[1];
p[1]=aux;
}
long long sens(punct a,punct b,punct c)
{
//functie ce determina daca 3 puncte sunt in sens trigonometric sau orar
long long x;
x=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (x>0)
return 1;
return 0;
}
void panta(punct &a)
{
//functia ce asociaza panta fiecarui punct
a.p=(-alfa.y+a.y)/(-alfa.x+a.x);
}
int cmp(punct a,punct b)
{
//functia de comparare pentru sortarea din stl
if (a.p==b.p)
return a.x<b.x;
return a.p<b.p;
}
int main()
{
int i,k=0,zz;
citire();
cauta_extrema();
for (i=1;i<=n;i++)
panta(p[i]);
sort(p+2,p+n+1,cmp);
ofstream out("infasuratoare.out");
sol[++k]=1;
sol[++k]=2;
//la sfarsitul vectoruliui pun din nou primul punct pentru a avea un poligon inchis
p[n+1]=p[1];
for (i=3;i<=n;i++)
{
//in while se elimina puncte pana cand ultimele 3 puncte sunt in sens trigonometric
while (!sens(p[sol[k-1]],p[sol[k]],p[i])&&k>2)
k--;
sol[++k]=i;
}
out<<k<<'\n';
i=k;
for (k=1;k<=i;k++)
out<<setprecision(20)<<p[sol[k]].x<<" "<<setprecision(20)<<p[sol[k]].y<<'\n';
}