Cod sursa(job #166149)

Utilizator scvalexAlexandru Scvortov scvalex Data 27 martie 2008 15:14:29
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define car first
#define cdr second
#define INF 1e10
#define e 1e-5

typedef pair<double, double> dpair;

int N;
vector<dpair> p;

inline void getCoef(double &A, double &B, double &C, const dpair &a, const dpair &b) {
	A = b.cdr - a.cdr;
	B = a.car - b.car;
	C = a.cdr*b.car - a.car*b.cdr;
}

inline int sign(double A, double B, double C, const dpair &pct) {
	double D = A*pct.car + B*pct.cdr + C;
	if (D > e)
		return 1;
	if (D < -e)
		return -1;
	return 0;
}

inline dpair intersect(double A1, double B1, double C1, const dpair &pct1, const dpair &pct2) {
	double A2, B2, C2;
	getCoef(A2, B2, C2, pct1, pct2);

	double det = A1*B2 - A2*B1;
	double X = (B1*C2 - B2*C1) / det;
	double Y = (A2*C1 - A1*C2) / det;

	return make_pair(X, Y);
}

inline double getArea() {
	vector<dpair> cp, ncp;
	cp.push_back(make_pair(-INF, -INF));
	cp.push_back(make_pair(-INF, INF));
	cp.push_back(make_pair(INF, INF));
	cp.push_back(make_pair(INF, -INF));
	cp.push_back(cp.front());

	double A, B, C;
	for (int i(0); i < N; ++i) {
		getCoef(A, B, C, p[i], p[i+1]);

		ncp.clear();
		for (int k(0); k + 1 < (int)cp.size(); ++k) {
			int sgnCur = sign(A, B, C, cp[k]);
			int sgnNxt = sign(A, B, C, cp[k+1]);

			if (sgnCur >= 0 && sgnNxt >= 0)
				ncp.push_back(cp[k]);
			else if (sgnCur < 0 && sgnNxt >= 0)
				ncp.push_back(intersect(A, B, C, cp[k], cp[k+1]));
			else if (sgnCur >= 0 && sgnNxt < 0) {
				ncp.push_back(cp[k]);
				if (sgnCur > 0)
					ncp.push_back(intersect(A, B, C, cp[k], cp[k+1]));
			} else if (sgnCur < 0 && sgnNxt < 0)
				;
		}
		ncp.push_back(ncp.front());
		cp = ncp;
	}

	double S(0);
	for (int k(0); k + 1 < (int)cp.size(); ++k)
		S += cp[k].car*cp[k+1].cdr - cp[k].cdr*cp[k+1].car;
	S = fabs(S) * 0.5;
	return S;
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("camera.in", "r");
	fscanf(fi, "%d", &N);
	double x, y;
	for (int i(0); i < N; ++i) {
		fscanf(fi, "%lf %lf", &x, &y);
		p.push_back(make_pair(x, y));
	}
	p.push_back(p.front());
	fclose(fi);

	double S = getArea();
	if (S < e) {
		reverse(p.begin(), p.end());
		S = getArea();
	}

	FILE *fo = fopen("camera.out", "w");
	fprintf(fo, "%.2lf\n", S);
	fclose(fo);

	return 0;
}