Cod sursa(job #1813894)

Utilizator vladttturcuman vlad vladtt Data 23 noiembrie 2016 14:47:55
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>

#define eps 1e-12
#define NMax 121000
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Point
{
    ld x,y;
    bool operator< (const Point p) const
    {
        return (p.x!=x ? x<p.x : y<p.y);
    }

    Point operator- (Point p1)
    {
        Point result = *this;

        result.x -= p1.x;
        result.y -= p1.y;

        return result;
    }

    static ld Angle(Point p)
    {
        ld angle = atan2(p.y, p.x);
        angle = angle * 360 / (2*M_PI);
       /* if(angle<0)
            angle+=360;*/
        return angle;
    }
};

vector<Point> Q;

int n;
Point a[NMax];

ld Area(Point a,Point b,Point c)
{
    return (a.x*b.y + a.y*c.x + b.x * c.y) - (a.x * c.y + a.y * b.x + b.y * c.x);
}


void Remove(Point x)
{
    if(Q.size()<2)
        return;

    bool eliminate = 0;
    do{
        eliminate = false;
        ld QW = Area(Q[Q.size() - 2],Q[Q.size() - 1],x);
        if(QW > 0 && QW > eps )
        {
            eliminate = true;
            Q.pop_back();
        }

    }while(Q.size()>=2 && eliminate);
}

ld Angle(Point origin,Point p)
{
    ld result = Point::Angle(p-origin);
    return result;
}

bool AngleCompare(Point p1,Point p2)
{
    if(p1.y == 2)
        p1.y=2;
    return Angle(a[1],p1) > Angle(a[1],p2);
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;

    sort(a+1,a+n+1);

    sort(a+2,a+n+1,AngleCompare);

    Q.push_back(a[1]);

    for(int i=2;i<=n;i++)
    {
        Remove(a[i]);
        Q.push_back(a[i]);
    }

    Remove(a[1]);

    fout<<Q.size()<<'\n';
    fout<<std::setprecision(6)<<std::fixed;

    for(int i =Q.size()-1;i>=0;i--)
        fout<<Q[i].x<<' '<<Q[i].y<<'\n';

    return 0;
}