Cod sursa(job #1534899)

Utilizator sulzandreiandrei sulzandrei Data 24 noiembrie 2015 01:30:39
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 6.17 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
#define foreach(i,n) for(int i = 0; i < n ; i++)
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const double epsilon = 0.00000000000009;
//algoritmul lent infasuratoare convexa O(n^4)  http://gta.math.unibuc.ro/stup/geom_comp.pdf
struct Point
{
   double x,y;
   Point(){x = 0; y = 0;}
   Point(double xx,double yy){ x = xx; y = yy;}
   friend istream& operator >>(istream& i , Point& p);
   friend ostream& operator <<(ostream& o, Point&p);
   friend ostream& operator<<(ostream&o,const Point& p);
   bool operator !=(const Point& B);
   bool operator !=(const Point& B)const;
   bool operator ==(const Point&B)const;
   Point operator /=(double divide);
   Point operator +=(const Point&);
   double distanceFrom(const Point &B);
   double distanceFrom(const Point &B)const;
   bool isRight(const Point &A, const Point& B)const;
   bool isLeft(const Point &A, const Point& B)const;

};
double determinant(const Point&P, const Point& Q, const Point&R)
{
    return (Q.x*R.y +P.x*Q.y +R.x*P.y - Q.x*P.y - R.x*Q.y - P.x*R.y);
}
bool Point::isRight(const Point &A, const Point& B)const
{
    return (determinant(A,B,*this)<0);
}
bool Point::isLeft(const Point &A, const Point& B)const
{
     return (determinant(A,B,*this)>0);
}
Point Point::operator +=(const Point& B)
{
    x += B.x;
    y += B.y;
    return *this;
}
Point Point::operator /=(double divide)
{
    x /= divide;
    y /= divide;
    return *this;
}
bool Point::operator !=(const Point& B)
{
    if (x == B.x && y == B.y)
        return false;
    return true;
}
bool Point::operator ==(const Point&B)const
{
    if( x == B.x && y == B.y)
        return true;
    return false;
}
bool Point::operator !=(const Point& B)const
{
    if (x == B.x && y == B.y)
        return false;
    return true;
}
istream& operator>>(istream& i , Point& p)
{
    i>>p.x>>p.y;
    return i;
}
ostream& operator<<(ostream& o , Point&p)
{
    o<<fixed<<setprecision(12)<<p.x<<" "<<fixed<<setprecision(12)<<p.y<<'\n';
    return o;
}
ostream& operator<<(ostream&o,const Point& p)
{
    o<<fixed<<setprecision(6)<<p.x<<" "<<fixed<<setprecision(6)<<p.y<<'\n';
    return o;
}
Point gCenter(const vector<Point>& M)
{
    Point p;

    for(const auto& point:M)
        p += point;

    p /=M.size();

    return p;
}
double area( const Point& A, const Point& B, const Point& C)
{
    return abs((1.0/2.0)*(A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - A.x*C.y - A.y*B.x));
}
double Point::distanceFrom(const Point& B)
{
    return abs(sqrt( (B.x-x)*(B.x-x) + (B.y - y)*(B.y - y) ));
}
double Point::distanceFrom(const Point& B)const
{
    return abs(sqrt( (B.x-x)*(B.x-x) + (B.y - y)*(B.y - y) ));
}
bool PinsideOrEdges(const Point& p, const Point& A, const Point& B, const Point& C)
{
    bool value = false;
    if ( abs((area(A,B,C)- (area(p,A,B)+area(p,A,C)+area(p,B,C)) )) <epsilon)
        value = true;
    if ( abs( A.distanceFrom(B) - (A.distanceFrom(p) + p.distanceFrom(B) ) ) <epsilon && p!=A && p!= B)
        value = true;
    if ( abs(A.distanceFrom(C) - (A.distanceFrom(p) + p.distanceFrom(C) ) ) <epsilon && p!=A && p!= C)
        value = true;
    if ( abs(B.distanceFrom(C) - (B.distanceFrom(p) + p.distanceFrom(C) ) ) <epsilon && p!=B && p!= C)
        value = true;
    return value;
}
int main()
{
    vector<Point> P;
    /*vector<Point> M;algoritm lent 1
    bool valid;
    Point cGen;*/
    int n;
    in>>n;
    Point p;
    foreach(i,n)
    {
        in>>p;
        P.push_back(p);
    }
    /* algoritm lent 1
    for(const auto& p:P)
    {
        valid = true;
        for(const auto& A:P)
            for(const auto& B:P)
                for(const auto& C:P)
                    if (A!=p && B!=p && C!=p && A!=B && A!=C && B!=C)
                        if (PinsideOrEdges(p,A,B,C))
                            valid = false;
        if( valid == true)
            M.push_back(p);
    }
    gCen = gCenter(M);
    sort(M.begin(),M.end(),[=](const Point& A,const Point& B){return atan2(A.y-gCen.y,A.x-gCen.x)<atan2(B.y-gCen.y,B.x-gCen.x); });
    out<<M.size()<<'\n';
    for(const auto& P:M)
        out<<P;*/
    vector<pair<Point,Point>>Eright,Eleft;
    vector<Point>L;
    bool valid;
    for(const auto& p:P)
        for(const auto& q:P)
            if(p != q)
            {
                valid = true;
                for(const auto& r:P)
                    if( r!=p && r!=q)
                        if (r.isRight(p,q))
                            valid = false;
                if(valid)
                    Eright.push_back(make_pair(p,q));
            }
    for(const auto& p:P)
        for(const auto& q:P)
            if(p != q)
            {
                valid = true;
                for(const auto& r:P)
                    if( r!=p && r!=q)
                        if (r.isLeft(p,q))
                            valid = false;
                if(valid)
                    Eleft.push_back(make_pair(p,q));
            }
    for(const auto& edges:Eright)
    {
        bool is = false;
        for(const auto& isin:L)
            if (isin == edges.first)
                is = true;
        if(!is)
            L.push_back(edges.first);
        is = false;
        for(const auto& isin:L)
            if (isin == edges.second)
                is = true;
        if(!is)
            L.push_back(edges.second);
    }
    for(const auto& edges:Eleft)
    {
        bool is = false;
        for(const auto& isin:L)
            if (isin == edges.first)
                is = true;
        if(!is)
            L.push_back(edges.first);
        is = false;
        for(const auto& isin:L)
            if (isin == edges.second)
                is = true;
        if(!is)
            L.push_back(edges.second);
    }
    Point gCen = gCenter(L);
    sort(L.begin(),L.end(),[=](const Point& A,const Point& B)->bool{return atan2(A.y-gCen.y,A.x-gCen.x)<atan2(B.y-gCen.y,B.x-gCen.x); });
    out<<L.size()<<'\n';
    for(const auto& p:L)
        out<<p;

    return 0;
}