Pagini recente » Cod sursa (job #2862081) | Cod sursa (job #814412) | Cod sursa (job #1394778) | Cod sursa (job #2935374) | Cod sursa (job #588430)
Cod sursa(job #588430)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
typedef struct
{
long double x;
long double y;
}
Coordonate;
long const Infinit=2000000000;
Coordonate P, Puncte[120001];
long N, PMin, Stiva[120001], lev=1;
void Read ()
{
ifstream fin ("infasuratoare.in");
long i;
Coordonate Aux;
P.x=Infinit;
P.y=Infinit;
fin >> N;
for (i=0; i<N; i++)
{
fin >> Puncte[i].x >> Puncte[i].y;
if ((Puncte[i].y<P.y)||((Puncte[i].y==P.y)&&(Puncte[i].x<P.x)))
{
P=Puncte[i];
PMin=i;
}
}
Aux=Puncte[0];
Puncte[0]=Puncte[PMin];
Puncte[PMin]=Aux;
fin.close ();
}
void Type ()
{
ofstream fout ("infasuratoare.out");
long i;
fout << lev << "\n";
for (i=0; i<lev; i++)
{
fout << Puncte[Stiva[i]].x << " " << Puncte[Stiva[i]].y << "\n";
}
fout.close ();
}
bool cmp(Coordonate a, Coordonate b)
{
if (((a.x-P.x)*(b.y-P.y))>((a.y-P.y)*(b.x-P.x)))
{
return true;
}
else
{
return false;
}
}
long double det(long double x1, long double y1, long double z1,long double x2, long double y2, long double z2, long double x3, long double y3, long double z3)
{
return (x1*y2*z3 + x2*y3*z1 + x3*y1*z2 - z1*y2*x3 - z2*y3*x1 - z3*y1*x2);
}
int main ()
{
long i;
Read ();
sort (Puncte+1, Puncte+N, cmp);
Stiva[0]=0;
Stiva[1]=1;
for(i=2;i<=N;++i)
{
while(lev>=1 && det(Puncte[Stiva[lev-1]].x, Puncte[Stiva[lev-1]].y, 1.0f, Puncte[Stiva[lev]].x, Puncte[Stiva[lev]].y, 1.0f, Puncte[i].x, Puncte[i].y, 1.0f) < 0)
--lev;
Stiva[++lev] = i;
}
Type ();
return 0;
}