Cod sursa(job #1431161)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 9 mai 2015 01:04:42
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

FILE *fin = fopen("infasuratoare.in" ,"r");
FILE *fout= fopen("infasuratoare.out","w");

int N;
const int Nmax = 120010;
struct Point{
    double x, y;
} P[Nmax];

vector <int> Stack;

void SetUp(){
    fscanf(fin, "%d", &N);
    for(int i = 1; i <= N; i ++)
        fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
    return;
}

inline double Area(Point &P1, Point &P2, Point &P3){
    return
        + P1.x * P2.y - P1.y * P2.x
        + P2.x * P3.y - P2.y * P3.x
        + P3.x * P1.y - P3.y * P1.x;
}

inline int cmp(Point P1, Point P2){
    return Area(P[1], P1, P2) > 0;
}

void CodeExpert(){
    for(int i = 2; i <= N; i ++){
        if(P[1].x > P[i].x)
            swap(P[1], P[i]);
    }
    sort(P + 1, P + N + 1, cmp);
    Stack.push_back(1);
    for(int i = 2; i <= N; i++){
        while(Stack.size() > 1 && (Area(P[Stack[Stack.size() - 2]], P[Stack[Stack.size() - 1]] , P[i])) <= 0)
            Stack.pop_back();
        Stack.push_back(i);
    }
    fprintf(fout, "%d\n", Stack.size());
    for(int i = 0; i < Stack.size(); i ++)
        fprintf(fout, "%.12f %.12f\n", P[Stack[i]].x, P[Stack[i]].y);
    return;
}

int main(){
    SetUp();
    CodeExpert();
    return 0;
}