Cod sursa(job #969526)

Utilizator p33l0lol peelola p33l0 Data 4 iulie 2013 15:44:00
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include <iostream>
#include <iomanip>
#include <cmath>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

#define F first
#define S second
using namespace std;

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");

    int n;
    fin>>n;

    vector< pair<double, double> > p;
    for(int i=0; i<n; ++i) {
        pair<double, double> q;
        fin>>q.F>>q.S;
        p.push_back(q);
    }
    double pi=atan(1)*4;
    sort(p.begin(), p.end());
    //for(int i=0; i<p.size(); ++i) {
        //cout<<p[i].F<<' '<<p[i].S<<'\n';
    //}
    //cout<<'\n';
    double ed=pi;
    vector<pair<double, double> > vast;
    vast.push_back(p[0]);
    for(int i=0; ;++i) {

        if(vast[0]==vast[i] && i!=0) break;
        int parask;
        double paras=9999999;
        double lolk=0;
        //cout<<ed*180/pi<<' ';
        for(int j=0; j<n; ++j) {
            if(vast[i]==p[j]) {
                //cout<<"ohi ";
                continue;
            }
            double kulma;
            if(p[j].F-vast[i].F==0) {
                if(p[j].S-vast[i].S>=0) kulma=pi;
                else kulma=0;
                goto ohi;
            }
            kulma=atan((p[j].S-vast[i].S)/(p[j].F-vast[i].F)); 
            if(p[j].F>vast[i].F) {
                kulma+=pi/2;
            }
            else kulma+=pi*1.5;
            ohi:; 
            if(kulma<=ed) {
               double ero=ed-kulma; 
               if(ero<paras) {
                   paras=ero;
                   parask=j;
                   lolk=kulma;
               }
            }
            if(kulma>ed) {
                double ero=2*pi-kulma+ed;
                if(ero<paras) { 
                    paras=ero;
                    parask=j;
                    lolk=kulma;
                }
            }
            //cout<<kulma*180/pi<<' '; 
            
        }
        //cout<<"paras kulma oli: "<<lolk*180/pi;
        //cout<<'\n';
        vast.push_back(p[parask]);
        ed=lolk;
    }
    fout<<vast.size()-1<<'\n';
    fout<<fixed;
    for(int i=vast.size()-2; i>=0; --i) {
        fout<<setprecision(6)<<vast[i].F<<' '<<vast[i].S<<'\n';
    }
}