Cod sursa(job #559151)

Utilizator sodamngoodSo Damn Good sodamngood Data 17 martie 2011 17:11:35
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define maxn 100010
#define pii pair<double, double>
#define x first
#define y second

int N, top;
int stiva[2 * maxn];
pii P[maxn];
vector<pii> sol;

int cmp(pii a, pii b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

double produs(pii p1, pii p2, pii p3) {
    double A = p1.y - p2.y;
    double B = p2.x - p1.x;
    double C = p1.x * p2.y - p1.y * p2.x;

    return A * p3.x + B * p3.y + C;
}

int main() {
    FILE *f1=fopen("infasuratoare.in", "r"), *f2=fopen("infasuratoare.out", "w");
    int i, j;

    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%lf %lf\n", &P[i].x, &P[i].y);
    }

    sort(P+1, P+N+1, cmp);

    top ++; stiva[top] = 1;
    top ++; stiva[top] = 2;
    for(i=3; i<=N; i++) {
         while(top > 1 && produs(P[ stiva[top-1] ], P[ stiva[top] ], P[i]) > 0) {
              top --;
         }
         top ++; stiva[top] = i;
    }

    for(i=1; i<=top; i++) {
         sol.push_back(P[ stiva[i] ]);
    }

    top = 1; stiva[top] = N;
    top = 2; stiva[top] = N - 1;
    for(i=N-2; i>=1; i--) {
         while(top > 1 && produs(P[ stiva[top-1] ], P[ stiva[top] ], P[i]) > 0) {
              top --;
         }
         top ++; stiva[top] = i;
    }

    for(i=2; i<top; i++) {
         sol.push_back(P[ stiva[i] ]);
    }

    fprintf(f2, "%d\n", sol.size());
    for(i=0; i<sol.size(); i++) {
         fprintf(f2, "%lf %lf\n", sol[i].x, sol[i].y);
    }

    fclose(f1); fclose(f2);
    return 0;
}