Cod sursa(job #1907067)

Utilizator marcdariaDaria Marc marcdaria Data 6 martie 2017 17:39:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Point
{
    double x,y;
};

vector<Point> v,h;
int N;

void Read();
double det(Point a, Point b, Point c);
bool comparePoints(Point a, Point b);
bool compareAngles(Point a, Point b);
void ConvexHull();


int main()
{
    Read();
    ConvexHull();

    fout<<fixed;
    fout<<h.size()<<'\n';

    for(int i=0;i<h.size();++i)
        fout<<setprecision(9)<<h[i].x<<" "<<h[i].y<<'\n';
    return 0;
}

void Read()
{
    fin>>N;
    v=vector<Point>(N+1);
    for(int i=0;i<N;++i)
        fin>>v[i].x>>v[i].y;
}
double det(Point a, Point b, Point c)
{
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool comparePoints(Point a, Point b)
{
    return (a.x<b.x)||(a.x==b.x)&&(a.y<b.y);
}
bool compareAngles(Point a, Point b)
{
    return det(v[0],a,b)<0;
}
void ConvexHull()
{
    swap(v[0],*min_element(v.begin(),v.end(),comparePoints));
    sort(v.begin()+1, v.end(),compareAngles);
    h.push_back(v[0]);
    h.push_back(v[1]);

    for(int i=2;i<v.size();++i)
    {
        while(h.size()>1 && det(*(h.end()-2), *(h.end()-1), v[i])>0)
            {h.erase(h.end()-1);}

        h.push_back(v[i]);
    }

    reverse(h.begin(),h.end());
}