Cod sursa(job #965975)

Utilizator p33l0lol peelola p33l0 Data 25 iunie 2013 00:05:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include <cmath>
#include <utility>
#include <bitset>
#include <fstream>
#define F first
#define S second
using namespace std;

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n;
    fin>>n;
    pair<double, double> p[120000];
    for(int i=0; i<n; ++i) {
        fin>>p[i].F>>p[i].S;
    }
    pair<double, double> v[120000]; 
    bitset<120000> kay;
    double pie=1e10;
    int piek=0;
    for(int i=0; i<n; ++i) {
        if(pie>p[i].F) {
            pie=p[i].F;
            piek=i;
        }
    }
    v[0].F=p[piek].F;
    v[0].S=p[piek].S;
    kay[piek]=1;
    double pi = atan(1) * 4;
    int k=1;
    double ed=pi/2;
    for(int i=0;;++i) {
        cout<<v[i].F<<' '<<v[i].S<<'\n';
        double upie=9999999999;
        double ukul=0;
        int loli=0;
        pair<double, double> lol;
        if(v[i]==v[0]&&i) break;
        for(int j=0; j<n; ++j) {
        //    cout<<j<<'\n';
            double ku=atan((p[j].S-v[i].S)/(p[j].F-v[i].F));            
            if(v[i]==p[j]) continue;
            if(v[i].F==p[j].F) {
                if(p[j].S>v[i].S) {
                    ku=pi/2;
                }
                else ku = pi*1.5;
            }
            else if(p[j].F<v[i].F) {
                ku+=pi;
            }
            else if(p[j].S<v[i].S) {
                ku+=pi*2;
            }
            ku = fmod(ku, 2*pi);
            cout<<(ku*180)/pi<<' '<<ed*180/pi<<' '<<abs(ku-ed)<<' '<<2*pi - max(ku, ed) + min(ku, ed)<<'\n';
            if(ku>ed) {
               double lol2=2*pi-ku + ed; 
               if(lol2<upie) {
                   upie=lol2;
                   ukul=ku;
                   lol=p[j];
                   loli=j;
               }
            }
            else {
                if(abs(ku-ed)<upie) {
                    upie=abs(ku-ed);
                    ukul=ku;
                    lol=p[j];
                    loli=j;
                } 
            }
        }
        
        v[k]=lol;
        ed=ukul;
        kay[loli]=1;
        ++k;
    }
    fout<<k<<'\n';
    for(int i=0; i<k+1; ++i) {
        fout<<v[i].F<<' '<<v[i].S<<'\n';
    }
    fin.close();
    fout.close();
}