Cod sursa(job #2084717)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 9 decembrie 2017 11:40:35
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int MAXN = 520;

struct punct
{
    int x, y;
};

struct dreapta
{
    double a, b, c;
    dreapta(punct e, punct f)
    {
        a = e.y - f.y;
        b = f.x - e.x;
        c = e.x * f.y - f.x * e.y;
    }
};

int n;
punct s1[MAXN], s2[MAXN];

void citire()
{
    fin >> n;
    for (int i = 0; i < n; i++) {
        fin >> s1[i].x >> s1[i].y >> s2[i].x >> s2[i].y;
    }
}

int apartine(punct e, punct jos, punct sus)
{
    return e.x >= jos.x && e.x <= sus.x;
}

/// returneaza 1 daca segmentele se intersecteaza
int intersect(punct e1, punct e2, punct f1, punct f2)
{
    if (e1.x > e2.x)
        swap(e1, e2);
    if (f1.x > f2.x)
        swap(f1, f2);
    dreapta d1(e1, e2);
    dreapta d2(f1, f2);
    if (d1.a * d2.b == d2.a * d1.b) {
        /// dreptele sunt paralele
        if (d1.c == d2.c) {
            /// dreptele coincid
            return apartine(e1, f1, f2) || apartine(f1, e1, e2);
        }
        else
            return 0;
    }
    else {
        if (d1.a == 0)
            return intersect(f1, f2, e1, e2);
        double y = (1.0*d2.a*d1.c - d1.a*d2.c) / (d1.a * d2.b - d2.a * d1.b);
        double x = 1.0 * (-d1.c - d1.b*y) / d1.a;
        return (x >= e1.x && x <= e2.x) && (x >= f1.x && x <= f2.x)
                && y >= min(e1.y, e2.y) && y <= max(e1.y, e2.y)
                && y >= min(f1.y, f2.y) && y <= max(f1.y, f2.y);
    }
}

void solve()
{
    int rez = 0;
    for (int i = 0; i < n-1; i++)
        for (int j = i+1; j < n; j++)
            if (intersect(s1[i], s2[i], s1[j], s2[j]))
                rez++;
    fout << rez;
}

int main()
{
    citire();
    solve();

    return 0;
}