Cod sursa(job #1727246)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 10 iulie 2016 12:22:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 120000;

struct point
{
    double x;
    double y;
};

point p[MAXN+1], pivot;
int n;
vector <point> hull;

void readData()
{
    scanf("%d",&n);

    for(int i = 1; i <= n; i++)
        scanf("%lf %lf",&p[i].x,&p[i].y);
}

/*
inline double cross_product(const point& A, const point& B, const point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

inline int cmp(const point& p1, const point& p2) {
    return cross_product(p[1], p1, p2) < 0;
}*/


double crossProduct(point p1, point p2, point p3)
{
    double x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y, x3 = p3.x, y3 = p3.y;
    return x1*y2 + x2*y3 + x3*y1 - x3*y2 - x1*y3 - x2*y1;
}

bool cmp(point p1, point p2)
{
    return crossProduct(p[1],p1,p2) < 0;
}



void grahamScan()
{
    pivot = p[1];
    int pivotPosition= 1;
    for(int i = 2; i <= n; i++)
        if(pivot.y > p[i].y)
        {
            pivot = p[i];
            pivotPosition = i;
        }
        else
        if(pivot.y == p[i].y)
            if(pivot.x > p[i].x)
            {
                pivot = p[i];
                pivotPosition = i;
            }

    swap(p[1],p[pivotPosition]);
    sort(p+2,p+n+1,cmp);



    hull.push_back(pivot);
    hull.push_back(p[2]);

    for(int i = 3; i <= n; i++)
    {
        while(hull.size() >= 2 && crossProduct(hull[hull.size()-2],hull[hull.size()-1],p[i]) > 0)
            hull.pop_back();
        hull.push_back(p[i]);
    }



}




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

    readData();

    grahamScan();

    cout<<fixed;

    cout<<setprecision(9)<<hull.size()<<endl;


    for(int i = hull.size() - 1; i >= 0; i--)
        cout<<hull[i].x<<' '<<hull[i].y<<endl;

    //testCrossPorduct();

    return 0;
}