Pagini recente » Cod sursa (job #1137843) | Cod sursa (job #837067) | Cod sursa (job #1792718) | Cod sursa (job #156844) | Cod sursa (job #588440)
Cod sursa(job #588440)
#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[120100];
long N, PMin, Stiva[120100], In[120100], K;
void Read ()
{
ifstream fin ("infasuratoare.in");
long i;
Coordonate Aux;
P.x=Infinit;
P.y=Infinit;
fin >> N;
for (i=1; 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[1];
Puncte[1]=Puncte[PMin];
Puncte[PMin]=Aux;
fin.close ();
}
void Type ()
{
ofstream fout ("infasuratoare.out");
long i;
fout << K-1 << "\n";
for (i=1; i<K; 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;
}
}
inline double semn(Coordonate A, Coordonate B, Coordonate C)
{
return A.x * B.y + B.x * C.y + A.y * C.x - C.x * B.y - B.x * A.y - A.x * C.y;
}
int main ()
{
long i;
Read ();
sort (Puncte+2, Puncte+N+1, cmp);
Stiva[1]=1;
Stiva[2]=2;
K=2;
In[1]=1;
In[2]=1;
i=2;
while(i<=N)
{
i++;
while(K > 1 && semn(Puncte[Stiva[K]], Puncte[Stiva[K - 1]], Puncte[i]) > 0)
{
In[Stiva[K--]] = 0;
}
Stiva[++K] = i;
In[i] = 1;
}
Type ();
return 0;
}