Nu aveti permisiuni pentru a descarca fisierul grader_test1.ok
Cod sursa(job #388001)
Utilizator | Data | 28 ianuarie 2010 23:39:25 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.56 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 120010
struct punct {double x, y, ctg;} v[Nmax], aux;
void citire (), afisare ();
double xmin, ymin;
int pmin, n, N;
int S[Nmax];
int pozitie (long double x1, long double y1, long double x2, long double y2, long double x3, long double y3){
long double A;
A = (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1);
if (A >= 0) return 0;
return 1;
}
int cmp (const punct &a, const punct &b) {
return a.ctg > b.ctg;
}
void infasuratoare () {
aux = v[1]; v[1] = v[pmin]; v[pmin] = aux;
v[1].x = v[1].y = 0;
int i;
for (i = 2; i <= n; i++) {
v[i].x-= xmin;
v[i].y-= ymin;
v[i].ctg = v[i].x / v[i].y;
}
sort (v + 2, v + 1 + n, cmp);
v[n+1] = v[1];
S[++N] = 1;
for (i = 2; i <= n + 1; i++) {
while (N >= 2 && pozitie (v[S[N]].x, v[S[N]].y, v[S[N-1]].x, v[S[N-1]].y, v[i].x, v[i].y))
N--;
S[++N] = i;
}
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
citire ();
infasuratoare ();
afisare ();
return 0;
}
void citire () {
scanf ("%d", &n);
scanf ("%lf %lf", &v[1].x, &v[1].y);
xmin = v[1].x; ymin = v[1].y;
for (int i = 2; i <= n; i++) {
scanf ("%lf %lf", &v[i].x, &v[i].y);
if (ymin > v[i].y || ( ymin == v[i].y && xmin > v[i].x )) {
xmin = v[i].x;
ymin = v[i].y;
pmin = i;
}
}
}
void afisare () {
printf ("%d\n", N - 1);
for (int i = 1; i < N; i++)
printf ("%lf %lf\n", v[S[i]].x + xmin, v[S[i]].y + ymin);
}