Cod sursa(job #2531368)

Utilizator victorzarzuZarzu Victor victorzarzu Data 26 ianuarie 2020 10:42:20
Problema Camera Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define point pair<double,double>
#define DIM 1000

using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
char buffer[32010];
int poz = 31999;
int n;
double area;
double sumx,sumy;
vector<point> p,r,a;

bool cmp(point po1,point po2)
{
    return atan2(po1.x - sumx / n,po1.y - sumy / n) > atan2(po2.x - sumx / n,po2.y - sumy / n);
}

bool cmp1(point po1,point po2)
{
    return atan2(po1.x - sumx / r.size(),po1.y - sumy / r.size()) > atan2(po2.x - sumx / r.size(),po2.y - sumy / r.size());
}

void inc()
{
    poz++;
    if(poz == 32000)
    {
        fread(buffer,1,32000,stdin);
        poz = 0;
    }
}

void read(int &x)
{
    char semn = '+';
    while(buffer[poz] < '0' || buffer[poz] > '9')
        {
            semn = buffer[poz];
            inc();
        }
    x = 0;
    while(buffer[poz] >= '0' && buffer[poz] <= '9')
    {
        x = x * 10 + buffer[poz] - '0';
        inc();
    }
    if(semn == '-')
        x = -x;
}

void Read()
{
    freopen("camera.in","r",stdin);
    int x,y;
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(x);
        read(y);
        sumx += x;
        sumy += y;
        p.push_back(make_pair(x,y));
    }
    sort(p.begin(),p.end(),cmp);
    r.assign(p.begin(),p.end());
}


point intersection(point po1,point po2,point po3,point po4)
{
    double x1 = po1.y - po2.y;
    double y1 = po2.x - po1.x;
    double c1 = po1.x * po2.y - po2.x * po1.y;
    double x2 = po3.y - po4.y;
    double y2 = po4.x - po3.x;
    double c2 = po3.x * po4.y - po4.x * po3.y;

    double x = (y1 * c2 - y2 * c1) / (x1 * y2 - x2 * y1);
    double y = (c2 * x1 - c1 * x2) / (y1 * x2 - y2 * x1);

    return {x , y};
}

void Prepare()
{
    r.clear();
    p.push_back(p[0]);
    p.push_back(p[1]);
    r.push_back(intersection(p[1],p[2],p[3],p[4]));
    r.push_back(intersection(p[1],p[2],p[4],p[5]));
    r.push_back(intersection(p[2],p[3],p[3],p[4]));
    r.push_back(intersection(p[2],p[3],p[5],p[4]));
    sumx = sumy = 0;
    for(int i=0;i<r.size();++i)
    {
        sumx += r[i].x;
        sumy += r[i].y;
    }
    sort(r.begin(),r.end(),cmp);
}

int cross_product(point po1,point po2,point po3)
{
    return (po2.y - po3.y) * (po1.x - po3.x) - (po1.y - po3.y) * (po2.x - po3.x);
}


void Solve()
{
    for(int i = 5;i < p.size() - 1;++i)
    {
        a.clear();

        r.push_back(r[0]);

        for(int j = 0;j < r.size() - 1;++j)
        {
            point curr = r[j];
            point next = r[j + 1];

            if(cross_product(p[i],p[i + 1],curr) > 0)
            {
                if(cross_product(p[i],p[i + 1],next) > 0)
                    a.push_back(next);
                else
                    a.push_back(intersection(p[i],p[i + 1],curr,next));
            }
            else
            {
                if(cross_product(p[i],p[i + 1],next) >= 0)
                {
                    a.push_back(intersection(p[i],p[i + 1],curr,next));
                    a.push_back(next);
                }
            }
        }

        r.clear();
        r.assign(a.begin(),a.end());
    }
}

void calculate_area()
{
    r.push_back(r[0]);
    for(int i = 0;i < r.size() - 1;++i)
        area += r[i].x * r[i + 1].y - r[i + 1].x * r[i].y;
    if(area < 0)
        area = -area;
    area /= 2.0;
}

void Print()
{
    g<<setprecision(2)<<fixed;
    g<<area;
    g.close();
}
int main()
{
    Read();
    if(n > 4)
    {
        Prepare();
        Solve();
    }
    calculate_area();
    Print();
    return 0;
}