Cod sursa(job #1114513)

Utilizator StefansebiStefan Sebastian Stefansebi Data 21 februarie 2014 18:29:27
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<iostream>
#include<cmath>
#include<algorithm>
#include<fstream>
#include<iomanip>
#define PI 3.14159265
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {
    double x; double y;
};
struct segment {
    punct a; punct b;
};
punct p0, p1, p2, p3, p4, p[120000], s[120000];
int n;
int varf;

int prod(punct p1, punct p2, punct p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

void afis(){
    int i; fout << fixed;
    fout << varf << '\n';
    for (i = varf; i >= 1; i--)
        fout << setprecision(9) << s[i].x << " " << s[i].y << '\n';
}

void afisn(){
    int i;
    fout << n << '\n';
    for (i = 1; i <= n; i++)
        fout  << p[i].x << " " << p[i].y << '\n';
}

void primul(){
    int i; int poz = 1;
    for (i = 1; i <= n; i++){
        if (p[poz].x > p[i].x)
            poz = i;
    }
    for (i = 3; i <= n; i++)
        if (p[poz].x == p[i].x and p[poz].y > p[i].y)
            poz = i;
    punct aux = p[1]; p[1] = p[poz]; p[poz] = aux;
}

int cmp(punct p1, punct p2) {
    return prod(p[1], p1, p2) < 0;
}

void graham(){
    int i; double o;
    primul();
    //afisn();
    sort(p + 2, p + n + 1, cmp);
   // afisn();
    varf = 2; s[1] = p[1]; s[2] = p[2];
    for (int i = 3; i <= n; ++i) {
        while (varf >= 2 && prod(s[varf - 1], s[varf], p[i]) > 0)
            --varf;
        s[++varf] = p[i];
    }
    afis();
}

int main() {
    fin >> n; int i;
    for (i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;
    graham();
}