Cod sursa(job #2084675)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 9 decembrie 2017 11:25:08
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>

using namespace std;

const int NMax = 505;

struct Segment
{
    int x1,y1,x2,y2;
}v[NMax];

int joi, n;

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

void Read()
{
    fin >> n;
    for(int i=1; i<=n; ++i)
    {
        fin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
    }
}

bool Checkx(double x, double y, Segment t1)
{
    int mini = min(t1.y1, t1.y2);
    int maxi = max(t1.y1, t1.y2);

    if(!(y >= mini && y<=maxi))
        return 0;

    mini = min(t1.x1, t1.x2);
    maxi = max(t1.x1, t1.x2);

    if(!(x>=mini && x<=maxi))
        return 0;

    return 1;
}


int Inters(Segment t1, Segment t2)
{
    double a1 = t1.y1 - t1.y2;
    double b1 = t1.x2 - t1.x1;
    double c1 = t1.x1 * t1.y2 - t1.x2 * t1.y1;

    double a2 = t2.y1 - t2.y2;
    double b2 = t2.x2 - t2.x1;
    double c2 = t2.x1 * t2.y2 - t2.x2 * t2.y1;

    double x_int, y_int;

    if(a1 == 0)
    {
        swap(a1,a2);
        swap(b1,b2);
        swap(c1,c2);
    }

    if(a1*b2 - a2*b1 == 0)
    {
        if(c1==c2)
        {
            int mini = min(max(t1.x1, t1.x2), max(t2.x1, t2.x2));
            int maxi = max(min(t1.x1, t1.x2), min(t2.x1, t2.x2));

            int ok = 1;
            if(!(mini >= maxi))
                ok = 0;

            mini = min(max(t1.y1, t1.y2), max(t2.y1, t2.y2));
            maxi = max(min(t1.y1, t1.y2), min(t2.y1, t2.y2));

            if(!(mini>=maxi))
                ok = 0;

            if(ok==1)
                return 1;
            else
                return 0;
        }

        else
            return 0;
    }

    else
        y_int = (double)(a2*c1 - a1*c2)/(a1*b2 - a2*b1);


    x_int = (double)(-c1 - b1 * y_int) / a1;

    if(Checkx(x_int, y_int, t1) && Checkx(x_int, y_int, t2))
        return 1;

    return 0;

}

void Solve()
{
    for(int i=1; i<n; ++i)
        for(int j=i+1; j<=n; ++j)
    {
        if(Inters(v[i],v[j]))
            ++joi;
    }
}

int main()
{
    Read();
    Solve();

    fout << joi;

    return 0;
}