Cod sursa(job #1728007)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 12 iulie 2016 01:14:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 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;
}