Cod sursa(job #1761682)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 22 septembrie 2016 18:10:39
Problema Camera Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <iostream>
#include <cstdio>
#define MAXN 2050
#define EPS 0.000001
#define MAXCOORD 110000

using namespace std;

int n;
pair<int, int> parc[MAXN];
struct coord
{
	double x;
	double y;
	coord(double x = 0, double y = -1) : x(x), y(y) { }
};

bool eq(double x, double y)
{
    return (x-y) > -EPS && (x-y) < EPS;
}

void citire()
{
	scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &parc[i].first, &parc[i].second);
	parc[n+1] = parc[1];
}

coord poli[4*MAXN];
coord temp[4*MAXN];
int nq;

int semicontains(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return (x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1*y3) < 0;
}

double det(double x1, double y1, double x2, double y2, double x3, double y3)
{
	return (x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1*y3);
}

coord intersect(double p1x1, double p1y1, double p1x2, double p1y2, double p2x1, double p2y1, double p2x2, double p2y2)
{
//	if (p1x1 == p1x2) {
//		double m2 = (p2y1 - p2y2) / (p2x1 - p2x2);
//		double c2 = (p2y1 - m2*p2x1);
//		return coord(p1x1, m2*p1x1 + c2);
//	}
//	if (p2x1 == p2x2) {
//		double m1 = (p1y1 - p1y2) / (p1x1 - p1x2);
//		double c1 = (p1y1 - m1*p1x1);
//		return coord(p2x1, m1*p2x1 + c1);
//	}
//    double m1 = (p1y1 - p1y2) / (p1x1 - p1x2);
//    double c1 = (p1y1 - m1*p1x1);
//	double m2 = (p2y1 - p2y2) / (p2x1 - p2x2);
//    double c2 = (p2y1 - m2*p2x1);
//
//    double x = (c2 - c1) / (m1 - m2);
//    double y = m1*x + c1;
//    return coord(x, y);

double A1,B1,C1,A2,B2,C2,D;

    A1=1.0*p1y2-p1y1;
    B1=p1x1-p1x2;
    C1=A1*p1x1+B1*p1y1;

    A2=1.0*p2y2-p2y1;
    B2=p2x1-p2x2;
    C2=A2*p2x1+B2*p2y1;

    D=A1*B2-A2*B1;

    if (eq(D, 0))
        return coord(p1x1, p1y1);

    return coord((B2*C1-B1*C2)/D,(A1*C2-A2*C1)/D);
}

void solve()
{
	poli[++nq] = coord(-MAXCOORD, -MAXCOORD);
	poli[++nq] = coord(-MAXCOORD, MAXCOORD);
	poli[++nq] = coord(MAXCOORD, MAXCOORD);
	poli[++nq] = coord(MAXCOORD, -MAXCOORD);
    for (int i = 1; i <= n; i++) {
		poli[nq+1] = poli[1];
        double x1 = parc[i].first;
        double y1 = parc[i].second;
        double x2 = parc[i+1].first;
        double y2 = parc[i+1].second;
		int rq = 0;
        for (int j = 1; j <= nq; j++) {
            int c1 = semicontains(x1, y1, x2, y2, poli[j].x, poli[j].y);
			int c2 = semicontains(x1, y1, x2, y2, poli[j+1].x, poli[j+1].y);
            if (!c1 && !c2)
				continue;
			else if (!c1 && c2) {
                temp[++rq] = intersect(x1, y1, x2, y2, poli[j].x, poli[j].y, poli[j+1].x, poli[j+1].y);
				temp[++rq] = coord(poli[j+1].x, poli[j+1].y);
			}
			else if (c1 && !c2)
                temp[++rq] = intersect(x1, y1, x2, y2, poli[j].x, poli[j].y, poli[j+1].x, poli[j+1].y);
			else
				temp[++rq] = coord(poli[j+1].x, poli[j+1].y);
        }
        nq = 0;
        for (int i = 1; i <= rq; i++)
			if (temp[i].x != temp[i-1].x || temp[i].y != temp[i-1].y)
				poli[++nq] = temp[i];
    }
}

double arie()
{
	poli[nq+1] = poli[1];
	double ar = 0;
	for (int i = 1; i <= nq; i++)
        ar += det(0, 0, poli[i].x, poli[i].y, poli[i+1].x, poli[i+1].y);
	ar *= (-0.5);
	return ar;
}

int main()
{
    freopen("camera.in", "r", stdin);
    freopen("camera.out", "w", stdout);

    citire();
    solve();
    printf("%.2lf", arie());

    return 0;
}