Cod sursa(job #1361664)

Utilizator ooptNemes Alin oopt Data 25 februarie 2015 22:49:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

#define pb push_back
 
const int maxn = 120000;
 
using namespace std;
 
vector<int> VECT;
double X[maxn],Y[maxn];
int N,VER[maxn];
 
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d\n",&N);
    X[0] = 1000000000;Y[0] = 1000000000;
    for(int i = 1;i <= N; ++i)
        scanf("%lf %lf\n",&X[i],&Y[i]);
    int punct_initial = 0;
    int cur = 0;
    int move = 1;
    for(int i = 1;i <= N; ++i)
        if (X[i] < X[punct_initial]) punct_initial = i;
    cur = punct_initial;
    double last = 0;
    
    while(move || punct_initial != cur) {
        move = 0;
        VECT.pb(cur);
        double ma = 10000;
        int poznoua = cur;
        for(int i = 1;i <= N; ++i) {
            if (VER[i] || i == cur) continue;
            double unghi = atan2((X[i] - X[cur]),Y[i] - Y[cur]);
            if (unghi < 0) unghi += 2* M_PI;
            if (ma > unghi) {ma = unghi; poznoua = i;}
        }
        cur = poznoua;
        VER[cur] = 1;
    }

    reverse(VECT.begin(),VECT.end());
    printf("%d\n",VECT.size());
    for(unsigned int i = 0;i < VECT.size(); ++i)
        printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);
    
    return 0;
}