Cod sursa(job #2756496)

Utilizator Stefan_GhinescuGhinescu Stefan-George Stefan_Ghinescu Data 1 iunie 2021 09:47:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.86 kb
#include <iostream>
#include <cmath>
#include <iomanip>

#if 0

using namespace std;

/*ifstream cin("uva10242.in");
ofstream cout("uva10242.out");*/

const double eps = 1.0e-14;

void afisare1(double x)
{
    int y = x * 1000;
    if (y % 1000 == 0)
    {
        cout << y * 0.001 << ".000";
        return;
    }
    if (y % 100 == 0)
    {
        cout << y * 0.001 << "00";
        return;
    }
    if (y % 10 == 0)
    {
        cout << y * 0.001 << "0";
        return;
    }
    else
    {
        cout << y * 0.001;
        return;
    }
}

void afisare(double x)
{
    cout << setprecision(3) << x;
}

int main()
{
	double x1, y1, x2, y2, x3, y3, x4, y4;
	cout << showpoint << fixed;
	while(!cin.eof())
    {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		if (cin.eof())
        {
            break;
        }
		if (fabs(x1 - x3) < eps && fabs(y1 - y3) < eps)
        {
            afisare((x2 + x4) - x1);
			cout << ' ';
			afisare((y2 + y4) - y1);
			cout << '\n';
        }
		else if (fabs(x1 - x4) < eps && fabs(y1 - y4) < eps)
        {
            afisare((x2 + x3) - x1);
			cout << ' ';
			afisare((y2 + y3) - y1);
			cout << '\n';
        }
		else if (fabs(x2 - x3) < eps && fabs(y2 - y3) < eps)
        {
			afisare((x1 + x4) - x2);
			cout << ' ';
			afisare((y1 + y4) - y2);
			cout << '\n';
        }
		else
        {
			afisare((x1 + x3) - x2);
			cout << ' ';
			afisare((y1 + y3) - y2);
			cout << '\n';
        }
	}
    return 0;
}
#endif

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

struct POINT
{
	double x, y;
    /*POINT(double a, double b)
        :x(a), y(b)
    {
    }*/
};

struct segment
{
    POINT A, B;
};

const double eps = 1.0e-14;
const double INF = 1e9;

double cp(const POINT& P1, const POINT& P2, const POINT& P3)
{
	return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}

int ccw(const POINT& P1, const POINT& P2, const POINT& P3)
{
	double crossprod = cp(P1, P2, P3);
	if (fabs(crossprod) < eps)
		return 0;
	if (crossprod >= eps)
		return 1;
	return -1;
}

double dist(POINT P1, POINT P2)
{
	return sqrt((P2.y - P1.y) * (P2.y - P1.y) + (P2.x - P1.x) * (P2.x - P1.x));
}

double slope(POINT P1, POINT P2)
{
	if (fabs(P1.x - P2.x) < eps)
		return INF;
	return (P2.y - P1.y) / (P2.x - P1.x);
}

int line_intersection(POINT P1, POINT P2, POINT P3, POINT P4, POINT& P0)
{
	double a1 = P1.y - P2.y, b1 = P2.x - P1.x, c1 = P1.x * P2.y - P2.x * P1.y, a2 = P3.y - P4.y, b2 = P4.x - P3.x, c2 = P3.x * P4.y - P4.x * P3.y;
	if (fabs(a1 * b2 - a2 * b1) < eps)
	{
		if (fabs(a1 * c2 - a2 * c1) < eps)
		{
			return -1;
		}
		else
		{
			return 0;
		}
	}
	else
	{
		P0.x = (-1 * c1 * b2 + c2 * b1) / (a1 * b2 - a2 * b1);
		P0.y = (-1 * a1 * c2 + a2 * c1) / (a1 * b2 - a2 * b1);
		return 1;
	}
}

bool point_in_box(const POINT& P1, const POINT& P2, const POINT& P3)
{
    POINT L, R;
    L.x = min(P1.x, P2.x);
    L.y = min(P1.y, P2.y);
    R.x = max(P1.x, P2.x);
    R.y = max(P1.y, P2.y);
    return L.x <= P3.x && P3.x <= R.x && L.y <= P3.y && P3.y <= R.y;
}

bool segm_intersection(const POINT& P1, const POINT& P2, const POINT& P3, const POINT& P4)
{
    int c1 = ccw(P1, P2, P3);
    int c2 = ccw(P1, P2, P4);
    int c3 = ccw(P3, P4, P1);
    int c4 = ccw(P3, P4, P2);
    if (c1 * c2 < 0 && c3 * c4 < 0)
        return 1;
    if ((c1 * c2 == 0 && c3 * c4 < 0) || (c1 * c2 < 0 && c3 * c4 == 0))
        return 1;
    if (c1 * c2 == 0 && c3 * c4 == 0)
        if (point_in_box(P1, P2, P3) || point_in_box(P1, P2, P4) || point_in_box(P3, P4, P1) || point_in_box(P3, P4, P2))
            return 1;
    return 0;

    /*POINT P0(0, 0);
    int a = line_intersection(P1, P2, P3, P4, P0);
    if (a == -1)
    {
        if (point_in_box(P2, P3, P1) && point_in_box(P2, P4, P1) && point_in_box(P3, P4, P1))
            return 1;
        return 0;
    }
    if (a == 0)
        return 0;
    if (a == 1)
    {
        if (dist(P1, P0) > dist(P1, P2) || dist(P2, P0) > dist(P1, P2))
            return 0;
        return 1;
    }*/
}

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

segment v[505];

int main()
{
    int n, i, j, k = 0;
    fin >> n;
    for (i = 0; i < n; ++i)
        fin >> v[i].A.x >> v[i].A.y >> v[i].B.x >> v[i].B.y;
    for (i = 0; i < n - 1; ++i)
    {
        for (j = i + 1; j < n; ++j)
        {
            if (segm_intersection(v[i].A, v[i].B, v[j].A, v[j].B))
            {
                /*cout << v[i].A.x << ' ' << v[i].A.y << ' ' << v[i].B.x << ' ' << v[i].B.y << ' ';
                cout << v[j].A.x << ' ' << v[j].A.y << ' ' << v[j].B.x << ' ' << v[j].B.y << ' ';
                cout << endl;*/
                ++k;
            }
        }
    }
    fout << k;
	return 0;
}