Pagini recente » Cod sursa (job #1279197) | Cod sursa (job #2786262) | Cod sursa (job #605775) | Cod sursa (job #93150) | Cod sursa (job #588445)
Cod sursa(job #588445)
#include <iostream>
#include <utility>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct
{
double x;
double y;
}
Coordonate;
const int Infinit=2000000000;
Coordonate P, Puncte[120100];
int N, PMin, Stiva[120100], In[120100], K;
void Read ()
{
freopen ("infasuratoare.in", "r", stdin);
long i;
Coordonate Aux;
P.x=Infinit;
P.y=Infinit;
scanf ("%d\n", &N);
for (i=1; i<=N; i++)
{
scanf ("%lf %lf", &Puncte[i].x, &Puncte[i].y);
if ((Puncte[i].x<P.x)||((Puncte[i].x==P.x)&&(Puncte[i].y<P.y)))
{
P=Puncte[i];
PMin=i;
}
}
Aux=Puncte[1];
Puncte[1]=Puncte[PMin];
Puncte[PMin]=Aux;
}
void Type ()
{
freopen ("infasuratoare.out", "w", stdout);
long i;
printf ("%d\n", K-1);
for (i=1; i<K; i++)
{
printf ("%lf %lf\n", Puncte[Stiva[i]].x, Puncte[Stiva[i]].y);
}
}
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;
}