Mai intai trebuie sa te autentifici.
Cod sursa(job #277543)
Utilizator | Data | 11 martie 2009 19:42:02 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.55 kb |
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"
#define MAX_N 120005
typedef struct point
{
double x, y;
};
point P[MAX_N];
int S[MAX_N];
int N, tp;
struct cmp
{
bool operator () (const point &a, const point &b)
{
if ((double) (a.x - P[1].x)*(b.y - P[1].y) > (double) (b.x - P[1].x)*(a.y - P[1].y)) return 1;
return 0;
}
};
inline int rotate (int a, int b, int c)
{
if ((P[a].x - P[c].x) * (P[b].y - P[c].y) - (P[b].x - P[c].x) * (P[a].y - P[c].y) > 0) return 0;
return 1;
}
int main ()
{
int i, m;
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d", &N);
for (i = 1; i <= N; ++i)
scanf ("%lf %lf", &P[i].x, &P[i].y);
for (i = 2, m = 1; i <= N; ++i)
if (P[i].y < P[m].y) m = i;
else
if (P[i].y == P[m].y && P[i].x < P[m].x) m = i;
point p = P[1]; P[1] = P[m], P[m] = p;
sort (P + 2, P + N + 1, cmp());
S[tp = 1] = 1;
for (i = 1; i <= N; ++i)
{
while (tp >= 2 && rotate (S[tp - 1], S[tp], i)) --tp;
S[++tp] = i;
}
printf ("%d\n", tp);
for (i = 1; i <= tp; ++i)
printf ("%lf %lf\n", P[S[i]].x, P[S[i]].y);
return 0;
}