Pagini recente » Cod sursa (job #1887968) | Cod sursa (job #896564) | Cod sursa (job #2479940) | Cod sursa (job #1796683) | Cod sursa (job #518744)
Cod sursa(job #518744)
#include<fstream>
#include<algorithm>
using namespace std;
#define NMAX 120010
const char infile[]="infasuratoare.in";
const char outfile[]="infasuratoare.out";
struct punct
{
double x;
double y;
};
int S[NMAX];
int k=0;
int N;
int C;
punct Start;
punct A[NMAX];
inline double produs(punct a,punct b,punct c)
{
return ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y));
}
void citire()
{
fstream fin(infile,ios::in);
fin>>N;
int indice;
double min=1000000010;
for(int i=1;i<=N;i++)
{
fin>>A[i].x>>A[i].y;
if(A[i].x<min)
{
min=A[i].x;
indice=i;
}
else if(A[i].x==min && A[i].y<A[indice].y)
{
min=A[i].x;
indice=i;
}
}
Start.x=A[indice].x;
Start.y=A[indice].y;
swap(A[1],A[indice]);
fin.close();
}
bool f(punct a,punct b)
{
double x,y;
x=(a.y-Start.y)/(a.x-Start.x);
y=(b.y-Start.y)/(b.x-Start.x);
return x<y;
}
void afisare()
{
fstream fout(outfile,ios::out);
fout<<k<<"\n";
for(int i=1;i<=k;i++)
fout<<A[S[i]].x<<" "<<A[S[i]].y<<"\n";
fout.close();
}
void Graham()
{
double x;
k++;
S[k]=1;
k++;
S[k]=2;
for(int i=3;i<=N;i++)
{
x=produs(A[S[k-1]],A[S[k]],A[i]);
if(x<0)
{
S[k]=i;
}
else
{
k++;
S[k]=i;
}
}
}
int main()
{
citire();
sort(A+2,A+N+1,f);
Graham();
afisare();
}