Cod sursa(job #1114904)

Utilizator StefansebiStefan Sebastian Stefansebi Data 21 februarie 2014 19:50:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 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;
};
punct p0, p1, p2, p3, p4, p[120000], s[120000];
int n;
int varf;

void push(punct p){
    ++varf; s[varf] = p;
}

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';
}

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

void infas(){
    int i; double o; int poz = 1;
    for (int i = 2; i <= n; ++i){
        if (p[i].y < p[poz].y)
            poz = i;
        else if (p[i].y == p[poz].y and p[i].x < p[poz].x)
            poz = i;
    }
    swap(p[1], p[poz]);
    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++) {
        o = prod(s[varf - 1], s[varf], p[i]);
        if (o == 0){
            varf--;
            push(p[i]); }
            else
            if (o > 0) push(p[i]);
                else {
                    while (o <= 0 and varf  >= 2){
                        varf--;
                        o = prod(s[varf - 1], s[varf], p[i]);
                    }
                    push(p[i]);
                }
    }
    afis();
}

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