Cod sursa(job #3210151)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 5 martie 2024 11:31:13
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <bits/stdc++.h>

#define inf 100000
#define NMAX 2005
#define eps 1e-6
using namespace std;

ifstream fin("camera.in");
ofstream fout("camera.out");

struct chestie{
    double x, y;
}pnct[NMAX];

double det(chestie a, chestie b, chestie c){
    return (a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - a.y * b.x - a.x * c.y);
}

chestie orig;
vector<chestie> poligIntersect;

int smn(double val){
    if(-eps < val && val < eps)
        return 0;
    if(val > eps)
        return 1;
    return -1;
}

chestie intersect(chestie a, chestie b, chestie c, chestie d){
    double a1 = b.y - a.y;
    double b1 = a.x - b.x;
    double c1 = a.y * b.x - a.x * b.y;

    double a2 = d.y - c.y;
    double b2 = c.x - d.x;
    double c2 = c.y * d.x - c.x * d.y;

    chestie rez;
    rez.x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
    rez.y = (c1 * a2 - c2 * a1) / (a1 * b2 - a2 * b1);
    return rez;
}

void newInter(chestie a, chestie b){
    vector<chestie> aux;
    poligIntersect.push_back(poligIntersect[0]);
    for(int i = 0; i < (int)poligIntersect.size() - 1; ++i)
    {
        int semn1 = smn(det(a, b, poligIntersect[i]));
        int semn2 = smn(det(a, b, poligIntersect[i + 1]));
        //fout<<semn1<<" "<<semn2<<'\n';
        if(semn1 * semn2 == -1)
        {
            aux.push_back(intersect(a, b, poligIntersect[i], poligIntersect[i + 1]));
        }
        if(semn2 >= 0)
            aux.push_back(poligIntersect[i + 1]);
    }
    poligIntersect = aux;
}

int main()
{
    int n;
    fin >> n;

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

    double ar = 0;
    for(int i = 1; i < n; ++i)
        ar += det(pnct[i], pnct[i + 1], orig);
    if(ar < 0)
        reverse(pnct + 1, pnct + n + 1);

    pnct[++n] = pnct[1];
    poligIntersect.push_back({-inf, -inf});
    poligIntersect.push_back({inf, -inf});
    poligIntersect.push_back({inf, inf});
    poligIntersect.push_back({-inf, inf});
    for(int i = 1; i < n; ++i)
        newInter(pnct[i], pnct[i + 1]);
   // for(int i=0;i<poligIntersect.size();i++)
       //fout<<poligIntersect[i].x<<" "<<poligIntersect[i].y<<'\n';
    if(poligIntersect.size() == 0)
    {
        fout << 0 << '\n';
        return 0;
    }

    poligIntersect.push_back(poligIntersect[0]);
    ar = 0;
    for(int i = 0; i < (int)(poligIntersect.size() - 1); ++i)
        ar += det(poligIntersect[i], poligIntersect[i + 1], orig);
    ar /= 2;
    ar = abs(ar);
    fout << fixed << setprecision(2) << ar << '\n';
    return 0;
}