Cod sursa(job #3203215)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 13 februarie 2024 12:21:43
Problema Camera Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n;
const int nmax = 2000;

struct point{
double x;
double y;
}v[nmax + 5],mn,mx;
struct general_equation{
double a;
double b;
double c;
    general_equation(point p1,point p2)
    {
        a = p1.y-p2.y;
        b = p2.x-p1.x;
        c = (p1.x-p2.x)*p1.y + (p2.y-p1.y)*p1.x;
    }


};



/*
ax ay 1
bx by 1
cx cy 1

bx-ax)(cy-ay) - (cx-ax)(by-ay) */

double det(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
bool outside(point a,point b,point c)
{
    return det(a,b,c)<0;
}
bool inside(point a,point b,point c)
{
    return !outside(a,b,c);
}

point intersection(general_equation l1,general_equation l2)
{
    point sol={0,0};
    sol.x = (l2.c * l1.b - l1.c * l2.b)/(l1.a*l2.b-l2.a*l1.b);
    sol.y = (l1.a * l2.c - l2.a*l1.c)/(l2.a*l1.b - l1.a*l2.b);
    return sol;
    /*
    l1.a * x +  l1.b * y + l1.c = 0 | l2.b
    l2.a * x +  l2.b * y + l2.c = 0 | l1.b

    l1.a * x * l2.b + l1.b*l2.b*y + l1.c*l2.b  = 0
    l2.a * x * l1.b + l1.b*l2.b*y + l2.c*l1.b = 0

    l1.a * x * l2.b - l2.a*x*l1.b + l1.c*l2.b - l2.c*l1.b =0
    x(l1.a * l2.b - l2.a*l1.b) = l2.c*l1.b - l1.c*l2.b

    l1.a * x +  l1.b * y + l1.c = 0 | l2.a
    l2.a * x +  l2.b * y + l2.c = 0 | l1.a

    l1.a * l2.a * x + l2.a*l1.b*y + l2.a*l1.c=0
    l1.a * l2.a * x + l1.a*l2.b*y + l1.a*l2.c=0

    y(l2.a*l1.b -l1.a*l2.b) + l2.a*l1.c -l1.a*l2.c=0;

    */
}


void solve()
{
    mn={100005,100005};
    mx={-100005,-100005};
    for(int i=1;i<=n;i++){
        double x,y;
        fin>>x>>y;
        v[i]={x,y};
        mn.x=min(x,mn.x);
        mn.y=min(y,mn.y);
        mx.x=max(x,mx.x);
        mx.y=max(y,mx.y);
    }
    v[n+1]=v[1];
    vector <point> poly;
    poly.push_back(mn);
    poly.push_back({mx.x,mn.y});
    poly.push_back(mx);
    poly.push_back({mn.x,mx.y});
    poly.push_back(mn);


    for(int i=1;i<=n;i++)
    {
        point a = v[i];
        point b = v[i+1];
        vector<point> poly_aux;
        for(int j = 1;j<poly.size();j++)
        {
            point nxt = poly[j];
            point crt = poly[j-1];

            if(inside(a,b,nxt) && inside(a,b,crt))
                poly_aux.push_back(nxt);
            else if (inside(a,b,crt) && outside(a,b,nxt))
                poly_aux.push_back(intersection(general_equation(a,b),general_equation(crt,nxt)));
            else if (outside(a,b,crt) && inside(a,b,nxt))
            {
                poly_aux.push_back(intersection(general_equation(a,b),general_equation(crt,nxt)));
                poly_aux.push_back(nxt);
            }
        }

        poly.clear();
        for(auto& i : poly_aux)
            poly.push_back(i);

        fout<<poly.size()<<'\n';
    }
}

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