Cod sursa(job #902923)

Utilizator vendettaSalajan Razvan vendetta Data 1 martie 2013 17:29:01
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <iomanip>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

#define nmax 120005
#define ll long long
#define Eps 0.000000000001
#define inf (1<<30)

int n, St[nmax];
typedef struct{
    double x, y;
}camp;

camp v[nmax], Pct;

double modul(double X){
    if (X < 0.0) return X;
    return -X;
}

void citeste(){
    f >> n;
    int poz = 0;
    Pct.x = (double)inf; Pct.y = (double)inf;
    for(int i=1; i<=n; ++i){
        f >> v[i].x >> v[i].y;
        if (Pct.x > v[i].x){
            Pct.x = v[i].x; Pct.y = v[i].y;
            poz = i;
        }else if ( modul(Pct.x - v[i].x) < Eps ){
            if (Pct.y > v[i].y){
                Pct.x = v[i].x; Pct.y = v[i].y;
                poz = i;
            }
        }
    }
    swap(v[1], v[poz]);
}

struct cmp{
    bool operator()(camp A, camp B){
        return( (A.x - Pct.x)*(B.y-Pct.y) < (A.y-Pct.y)*(B.x - Pct.x) );
    }
};

double semn(int i, int j, int k){
    return( v[i].x*v[j].y + v[j].x*v[k].y + v[k].x*v[i].y - v[k].x*v[j].y - v[k].y*v[i].x - v[j].x*v[i].y );
}

void rezolva(){
    sort(v+2, v+n+1, cmp());// pe pozitia 1 e pct ales si pe el nu are rost sa il sortez
    //acum le am sortate; 1 punct e ala ales; (cel mai din stanga si cel mai de jos)
    // il iau pe urmatorul si apoi il iau pe al 3 si tot incep sa scot puncte cat timp sunt in stiva cel putin 2
    St[ ++St[0] ] = 1; St[ ++St[0] ] = 2;

    for(int i=3; i<=n; ++i){
        while( St[0] >= 2 && semn( St[ St[0]-1 ], St[ St[0] ], i ) >= 0.000000000000 ){
            --St[0];
        }
        St[ ++St[0] ] = i;
    }
    g << St[0] << "\n";
    g << fixed;
    for(int i=St[0]; i>=1; --i){
        g << setprecision(12) << v[ St[i] ].x << " " << v[ St[i] ].y << "\n";
    }
}

int main(){
    setprecision(12);

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}