Cod sursa(job #1370302)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 3 martie 2015 13:49:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int n, nq;
const double EPS = 1;

struct punct
{
    double x, y;
    punct(double x=0, double y=0) : x(x), y(y)
    {

    }
    bool operator()(punct a, punct b)
    {
        return (a.x == b.x ? a.y - b.y < 0.0001 : a.x - b.x < 0.0001);
    }

}a[120012];

void citire()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf %lf", &a[i].x, &a[i].y);
        //cin >> a[i].x;
       //cin >> a[i].y;
    }
}

int determinant(punct f, punct g, punct h)
{
    return f.x *(g.y-h.y) + h.x * (f.y-g.y) + g.x *(h.y-f.y);
}

double cross_product(punct O, punct A, punct B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

void operate(vector<punct> &st, punct g)
{
    while(st.size() >= 2 && determinant(st[st.size()-2], st[st.size()-1], g) < 0)//determinant(st[st.size()-1], st[st.size()-2], g) > 0.0001)
    {
        st.pop_back();
       // cerr << determinant(st[st.size()-1], st[st.size()-2], g) - cross_product(st[st.size()-1], st[st.size()-2], g);
        //cerr << "\n";
    }
    st.push_back(g);
}

void solve()
{
    sort(a, a+n, punct());
    vector<punct> st;
    st.push_back(a[0]); st.push_back(a[1]);
    for (int i = 2; i < n; i++)
        operate(st, a[i]);
   // vector<punct> st2;
    //st2.push_back(a[n-1]); st2.push_back(a[n-2]);
    for (int i = n-2; i >= 0; i--)
        operate(st, a[i]);
    st.pop_back();
    printf("%d\n", st.size());
    for (int i = 0; i < st.size(); i++)
        printf("%lf %lf\n", st[i]);
//    for (int j = 0; j < st2.size()-1; j++)
//        printf("%lf %lf\n", st2[j]);
}

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

    citire();
    solve();

    return 0;
}