Cod sursa(job #323194)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 11 iunie 2009 10:43:17
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define maxN    120100
#define EPS     1e-12
#define oo      15e8

typedef struct point point;
typedef struct line line;

int N;

struct point {
        double x, y;
} P[maxN], PI;

struct line {
        point a, b;
};

bool cmp_points (point a, point b) {
        return (double)(a.x - PI.x) * (b.y - PI.y) > (double)(b.x - PI.x) * (a.y - PI.y);  
}

double same (line l, point p1, point p2) {
        int dx1, dx2, dy1, dy2, dx, dy;
        
        dx = l.b.x - l.a.x; dy = l.b.y - l.a.y;
        dx1 = p1.x - l.a.x; dy1 = p1.y - l.a.y;
        dx2 = p2.x - l.b.x; dy2 = p2.y - l.b.y;
        
        return (dx * dy1 - dy * dx1) * (dx * dy2 - dy * dx2);
}

void convex_hull () {
        int M = 2, i;
        line l;
        
        for (i = 4; i <= N + 1; ++ i) {
                M += 2;
                
                do {
                        M --;
                        l.a = P[M];
                        l.b = P[M - 1];
                } while (same (l, P[1], P[i]) < 0);
                
                swap (P[M + 1], P[i]);
        }
        
        printf("%d\n", M);
        
        for (i = 1; i <= M; ++ i)
                printf("%.6lf %.6lf\n", P[i].x, P[i].y);
}

int main () {
        int i, ind = 0;
        
        freopen("infasuratoare.in", "r", stdin);
        freopen("infasuratoare.out", "w", stdout);
        
        scanf("%d", &N);
        
        PI.x = oo; PI.y = oo;
        
        for (i = 1; i <= N; ++ i) {
                scanf("%lf%lf", &P[i].x, &P[i].y);
                if (PI.y > P[i].y || (PI.y == P[i].y && PI.x > P[i].x)) { PI = P[i]; ind = i; };
        }
        
        swap (P[1], P[ind]);
        
        sort (P + 2, P + N + 1, cmp_points);
        
        P[N + 1] = P[1];
       
       // for (i = 1; i <= N; ++ i)
       //         printf("%.2lf %.2lf\n", P[i].x, P[i].y);
                
        convex_hull ();
}