Pagini recente » Cod sursa (job #1301926) | Cod sursa (job #1331845) | Cod sursa (job #1798944) | Cod sursa (job #2146158) | Cod sursa (job #588450)
Cod sursa(job #588450)
#include <iostream>
#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], K;
void Read ()
{
FILE *fin = fopen ("infasuratoare.in", "r");
long i;
Coordonate Aux;
P.x=Infinit;
P.y=Infinit;
fscanf (fin, "%d\n", &N);
for (i=1; i<=N; i++)
{
fscanf (fin, "%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;
fclose (fin);
}
void Type ()
{
FILE *fout = fopen ("infasuratoare.out", "w");
long i;
fprintf (fout, "%d\n", K-1);
for (i=1; i<K; i++)
{
fprintf (fout, "%lf %lf\n", Puncte[Stiva[i]].x, Puncte[Stiva[i]].y);
}
fclose (fout);
}
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;
i=2;
while(i<=N)
{
i++;
while(K > 1 && Semn(Puncte[Stiva[K]], Puncte[Stiva[K - 1]], Puncte[i]) > 0)
{
K--;
}
Stiva[++K] = i;
}
Type ();
return 0;
}