Cod sursa(job #1412944)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 1 aprilie 2015 17:38:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <queue>
#include <iomanip>

using namespace std;

struct Pair{
    double x, y;
}eta;

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

vector < Pair > C;
vector <int> sol;
vector <int> S;
queue <int> Q;
int n, mini;

void citire()
{
    eta.x = 2000000000;
    Pair p;
    f>>n;
    for(int i=0; i<n; i++){
        f>>p.x>>p.y;
        C.push_back(p);
        if(p.x < eta.x || (p.x == eta.x && p.y < eta.y)){
            eta = p;
            mini = i;
        }
    }
    C[mini] = C[0];
    C[0] = eta;
}

int mycomp(Pair p1, Pair p2)
{
    double tg1, tg2;
    tg1 = (p1.y - eta.y) / (p1.x - eta.x);
    tg2 = (p2.y - eta.y) / (p2.x - eta.x);
    return tg1 < tg2;
}

void precalc()
{
    sort(C.begin() + 1, C.end(), mycomp);
}

double arie(Pair p1, Pair p2, Pair p3)
{
    double ar = 0;
    ar += (p1.x*p2.y + p2.x*p3.y + p1.y*p3.x)  -  (p3.x*p2.y + p1.x*p3.y + p1.y*p2.x);
    if(ar>0)
        return 1;
    return 0;
}

void rez()
{
    int i=2;
    S.push_back(0); S.push_back(1);
    while(S.size() >= 2 && i<n){
        for(; i<n && arie(C[S[S.size() - 2]], C[S.back()], C[i]); i++)
            S.push_back(i);
        if(i<n)
            S.pop_back();
    }
    if(S.size() > 2){
        g<<S.size()<<"\n";
        for(i=0; i<S.size(); i++){
            g<<fixed<<setprecision(6)<<C[S[i]].x<<" "<<C[S[i]].y<<"\n";
        }
    }
}

int main()
{
    citire();
    precalc();
    rez();
    return 0;
}