Pagini recente » Cod sursa (job #1678132) | Cod sursa (job #842117) | Cod sursa (job #1759768) | Cod sursa (job #50881) | Cod sursa (job #873259)
Cod sursa(job #873259)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define nmax 120001
#define eps 1e-6
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+p3.x*p1.y-p3.x*p2.y-p1.x*p3.y-p2.x*p1.y);
}
inline bool compara(punct p1,punct p2)
{
return (delta(pivot,p1,p2)>0);
}
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(P[i].x==pivot.x)
{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;
for(i=3;i<=N;i++)
{
while(M>=2 && delta(S[M-1],S[M],P[i])<=0)
--M;
S[++M]=P[i];
}
//pivot.x=0,pivot.y=0;
//sort(S+1,S+M+1,compara);
}
void scrie()
{
ofstream g("infasuratoare.out");
int i;
g<<fixed;
g<<M<<'\n';
g<<setprecision(6);
for(i=1;i<=M;i++)
g<<S[i].x<<' '<<S[i].y<<'\n';
g.close();
}
int main()
{
//cout << "Hello world!" << endl;
citeste();
rezolva_Graham();
scrie();
return 0;
}