Cod sursa(job #1534773)

Utilizator sulzandreiandrei sulzandrei Data 23 noiembrie 2015 23:02:52
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.23 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;
struct Point
{
   double x,y;
   Point(){x = 0; y = 0;}
   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;
   Point operator /=(double divide);
   Point operator +=(const Point&);
};
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 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(12)<<p.x<<" "<<fixed<<setprecision(12)<<p.y<<'\n';
    return o;
}
Point gCenter(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 distance(const Point& A, const Point& B)
{
    return abs(sqrt( (B.x-A.x)*(B.x-A.x) + (B.y - A.y)*(B.y - A.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((distance(A,B) - (distance(A,p) + distance(p,B)))) <epsilon && p!=A && p!= B)
        value = true;
    if ( abs((distance(A,C) - (distance(A,p) + distance(p,C)))) <epsilon && p!=A && p!= C)
        value = true;
    if ( abs((distance(B,C) - (distance(B,p) + distance(p,C)))) <epsilon && p!=B && p!= C)
        value = true;
    return value;
}
int main()
{
    vector<Point> P,M;
    bool valid;
    int n;
    in>>n;
    Point p,gCenter;
    foreach(i,n)
    {
        in>>p;
        P.push_back(p);
    }
    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);
    }
    //gCenter =gCenter(M);
    sort(M.begin(),M.end(),[](const Point& A,const Point& B)->bool{ return (atan(A.y/A.x)< atan(B.y/B.x)); });
    out<<M.size()<<'\n';
    for(const Point& P:M)
        out<<P;
    return 0;
}