Cod sursa(job #2523871)

Utilizator victorzarzuZarzu Victor victorzarzu Data 14 ianuarie 2020 20:31:18
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.82 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("arie.in");
ofstream g("arie.out");
int n,m;

struct point
{
    double x,y;
};

point s[50];
vector<point> p1;
vector<point> p2;
vector<point> p;
int head;
double sumx1,sumx2,sumy1,sumy2;

void Read()
{
    double x,y;
    f>>n;
    for(int i=1;i<=n;++i)
    {
        f>>x>>y;
        sumx1 += x;
        sumy1 += y;
        p1.push_back({x,y});
    }
    f>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        sumx2 += x;
        sumy2 += y;
        p2.push_back({x,y});
    }
    p1.push_back(p1[0]);
    p2.push_back(p2[0]);
    f.close();
}

bool cmp(point point1,point point2)
{
    return atan2(point1.x - sumx1/n,point1.y - sumy1/n) > atan2(point2.x - sumx2/m,point2.y - sumy2/m);
}

point intersection_point(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-y1*x2);
    double y;
    if(y1 != 0)
        y = (-c1-x1*x)/y1;
    else
        y = (-c2-x2*x)/y2;
    point result = {x,y};
    return result;
}

void find_intersections()
{
    for(int i=0;i<p1.size() - 1;++i)
    {
        for(int j=0;j<p2.size() - 1;++j)
        {
            point result = intersection_point(p1[i],p1[i+1],p2[j],p2[j+1]);
            if(result.x > max(p1[i].x,p1[i+1].x) || result.x > max(p2[j].x,p2[j+1].x) || result.x < min(p1[i].x,p1[i+1].x) || result.x < min(p2[j].x,p2[j+1].x) || result.y > max(p1[i].y,p1[i+1].y) || result.y > max(p2[j].y,p2[j+1].y) || result.y < min(p1[i].y,p1[i+1].y) || result.y < min(p2[j].y,p2[j+1].y))
                continue;
            if(isnan(result.x) && isnan(result.y))
                continue;
            p.push_back(result);
        }
    }
}

double calculate_area(point po1,point po2,point po3)
{
    return (po1.x*po2.y + po2.x*po3.y + po3.x*po1.y - po3.x*po2.y - po1.x*po3.y - po2.x*po1.y);
}

void find_points_inside()
{
    for(int i = 0;i < p1.size() - 1;++i)
    {
        double area1 = 0,area2 = 0;
        bool is_in = true;
        for(int j = 0;j < p2.size() - 1;++j)
            {
                area1 = calculate_area(p2[j],p2[j+1],p1[i]);
                if(area1 * area2 < 0)
                {
                    is_in = false;
                    break;
                }
                area2 = area1;
            }
        if(is_in) p.push_back(p1[i]);
    }
}

double cross_product(point A,point B,point C)
{
    return (B.y - C.y) * (A.x - C.x) - (A.y - C.y) * (B.x - C.x);
}

bool m_points(point A,point B)
{
    return cross_product(A,B,p[0]) < 0;
}

void Sort()
{
    sort(p.begin(),p.end(),cmp);
    int pos = 0;
    for(int i=0;i<p.size();++i)
        if(p[i].x < p[pos].x)
            pos = i;
        else if(p[i].x == p[pos].x && p[i].y < p[pos].y)
            pos = i;
    swap(p[pos],p[0]);
    sort(p.begin() + 1,p.end(),m_points);
}

void convex_hull()
{
    Sort();
    s[0] = p[0];
    s[1] = p[1];
    head = 1;
    for(int i=2;i<p.size();++i)
        {
            while(head >= 2 && cross_product(s[head - 1],s[head],p[i]) > 0)
                --head;
            s[++head] = p[i];
        }
}

double poligon_area()
{
    double area = 0;
    point po1 = {1000000001,1000000001};
    s[++head] = s[0];
    for(int i=0;i<head;++i)
        area += calculate_area(s[i],s[i+1],po1);
    if(area < 0) area *= -1;
    return (area / 2.0);
}

void Print()
{
    g<<setprecision(3)<<fixed;
    g<<poligon_area()<<'\n';
    g.close();
}

int main()
{
    Read();
    find_intersections();
    find_points_inside();
    convex_hull();
    Print();
    return 0;
}