Cod sursa(job #1883125)

Utilizator DanyBvGeorge-Daniel Gagiu DanyBv Data 17 februarie 2017 19:04:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX 120005
#define Punct pair<double, double>
#define X first
#define Y second

using namespace std;

Punct S[NMAX];
int n, k = 2;
double x, y;
Punct F;
vector<Punct> V;

double determinant(Punct a, Punct b, Punct c)
{
    return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
}

bool compare(Punct a, Punct b)
{
    return (determinant(F, a, b) > 0);
}

void read()
{
    freopen("infasuratoare.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%lf %lf", &x, &y);
        V.push_back(make_pair(x, y));
    }
    double minx = 0, miny = 0;
    for(int i = 0; i < n; i++)
        if(V[i].X < V[minx].X)
            minx = i;
    miny = minx;
    for(int i = 0; i < n; i++)
        if(V[i].X == V[minx].X && V[i].Y < V[miny].Y)
            miny = i;
    Punct aux;
    aux = V[0];
    V[0] = V[miny];
    V[miny] = aux;
    F = V[0];
}

void solve()
{
    sort(V.begin() + 1, V.end(), compare);
    for(int i = 0; i < 2; i++)
        S[i] = V[i];
    int j = 2;
    while(j < n)
    {
        while(determinant(V[k - 2], V[k - 1], V[j]) < 0 && k > 0)
            k--;
        V[k] = V[j++];
        k++;
    }
}

void print()
{
    freopen("infasuratoare.out", "w", stdout);
    for(int i = 1; i < k; i++)
        printf("%lf %lf\n", V[i].X, V[i].Y);
    printf("%lf %lf\n", V[0].X, V[0].Y);
}

int main()
{
    read();
    solve();
    print();
    //for(int i = 0; i < n; i++)
        //cerr << V[i].X << " " << V[i].Y << endl;
    return 0;
}