Cod sursa(job #967609)

Utilizator p33l0lol peelola p33l0 Data 28 iunie 2013 01:19:30
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 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() {
    int n;
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin>>n;

    vector< pair<double, double> > pist(n);
    for(int i=0; i<n; ++i) fin>>pist[i].F>>pist[i].S;
    sort(pist.begin(), pist.end());
    vector< pair<double, double> > vastaus;  
    vastaus.push_back(pist[0]); //eniten vasemmalla
    double pi=atan(1)*4;
    int edel=0;
    double ek=pi; //edellinen kulma
    for(int i=0;;++i) {
        if(vastaus[i]==vastaus[0] && i!=0) break;
        double pienin=9999999; //pienin ero edelliseen
        int pienink=0;//pienimmän koordinaatti
        double pieninkulma=0;
        for(int j=0; j<pist.size(); ++j) {
            if(j==edel) {
            continue; 
            }
            double uk=0;

            if(pist[j].F==pist[edel].F) {
                if(pist[j].S>=pist[edel].S) {
                    uk=pi;
                }
                else uk=0;
                goto ohi;
            }
            uk=atan((pist[j].S-pist[edel].S)/(pist[j].F-pist[edel].F));
            
            if(pist[j].F<pist[edel].F) {
                uk+=pi*1.5;
            }
            else uk+=pi/2;
            ohi:; 
            //cout<<uk*180/pi<<' ';
            double ero=0;
            if(uk<=ek) {
                ero=ek-uk; 
            }
            else {
                ero=2*pi-uk+ek;
            }
            if(ero<pienin) {
                pienink=j;
                pienin=ero;
                pieninkulma=uk;
            }


        }
        vastaus.push_back(pist[pienink]);
        edel=pienink;
        ek=pieninkulma;
    }
    fout<<vastaus.size()-1<<'\n';
    fout<<fixed;
    for(int i=vastaus.size()-2; i>=0; --i) {
        fout<<setprecision(6)<<vastaus[i].F<<' '<<vastaus[i].S<<'\n';
    }
    

}