Pagini recente » Cod sursa (job #1600400) | Cod sursa (job #498363) | Borderou de evaluare (job #2596983) | Cod sursa (job #1802127) | Cod sursa (job #870276)
Cod sursa(job #870276)
#include <fstream>
#include <cmath>
#include <algorithm>
#define nmax 12001
#define eps 1e-12
using namespace std;
struct punct{
double x,y;
};
punct P[nmax],S[nmax],pivot;
int N,M;
double distxy(punct &p1,punct &p2)
{
return((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
double delta(punct &P1,punct &P2,punct &P3)
{
return(
(P1.x*P2.y)+(P2.x*P3.y)+(P1.y*P3.x)-(P3.x*P2.y)-(P1.x*P3.y)-(P2.x*P1.y)
);
}
inline bool compara(punct p1,punct p2)
{
double dt=delta(pivot,p2,p1);
if(dt==0.0)
if(distxy(pivot,p1)>distxy(pivot,p2))
return true;
else
return false;
else
if(dt<0)
return true;
else
return false;
}
void citeste()
{
ifstream f("infasuratoare.in");
int i;
f>>N;
for(i=1;i<=N;i++)
f>>P[i].x>>P[i].y;
f.close();
}
void rezolva_Graham()
{
int i,indice;
punct aux;
pivot=P[1],indice=1;
for(i=2;i<=N;i++)
{
if(fabs(P[i].x-pivot.x)<=eps)
{if(P[i].y<pivot.y)
{pivot=P[i];
indice=i;
}}
else
if(P[i].x>pivot.x)
{
pivot=P[i];
indice=i;
}
}
aux=P[1];
P[1]=P[indice];
P[indice]=aux;
sort(P+2,P+N+1,compara);
S[1]=P[1];
S[2]=P[2];
M=2;
i=3;
while(i<=N)
{
if(delta(S[M-1],S[M],P[i])>0.f)
{
S[++M]=P[i];
i++;
}
else
--M;
}
}
void scrie()
{
ofstream g("infasuratoare.out");
int i;
g.precision(6);
g<<M<<'\n';
g<<S[M].x<<' '<<S[M].y<<'\n';
for(i=1;i<=M-1;i++)
g<<S[i].x<<' '<<S[i].y<<'\n';
g.close();
}
int main()
{
//cout << "Hello world!" << endl;
citeste();
rezolva_Graham();
scrie();
return 0;
}