Cod sursa(job #861156)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 21 ianuarie 2013 01:03:07
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>

using namespace std;

#define MAXN 120050
int N;
double X[MAXN], Y[MAXN];
bool used[MAXN];

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out","w", stdout);

    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%lf %lf", &X[i], &Y[i]);

    int first = 0;
    for(int i = 0; i < N; i++)
        if(Y[i] < Y[first])
            first = i;

    vector<int> parc;
    int crt = first;
    bool ok = true;
    double last = 0.0;

    while(crt != first || ok) {
        ok = false;
        int pmin = -1;
        parc.push_back(crt);
        double vmin = M_PI * 3;
        for(int i = 0; i < N; i++)
            if(!used[i] && i != crt) {
                double unghi = atan2(Y[i] - Y[crt], X[i] - X[crt]);

                if(unghi < 0)
                    unghi += 2 * M_PI;
                unghi -= last;
                if(unghi < 0)
                    unghi += 2 * M_PI;

                if(unghi < vmin) {
                    vmin = unghi;
                    pmin = i;
                }
            }

        last = vmin;

        used[pmin] = true;
        crt = pmin;
    }

    printf("%d\n", (int)parc.size());
    for(vector<int> :: iterator it = parc.begin(); it != parc.end(); it++)
        printf("%.6lf %.6lf\n", X[*it], Y[*it]);

	return 0;
}