Cod sursa(job #112228)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 3 decembrie 2007 21:39:38
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

typedef pair <double, double> coor;
#define x first
#define y second
#define MP make_pair

const int NMAX = 1 << 11;
const double VMAX = 1e+5;
const double eps = 1e-6;

int N, NP, ND;
coor A[NMAX], P[NMAX], D[NMAX];

void read(void) {
	FILE *fin = fopen("camera.in", "rt");
	int i;

	fscanf(fin, " %d", &N);

	for (i = 0; i < N; ++i)
		fscanf(fin, " %lf %lf", &A[i].x, &A[i].y);
	A[N] = A[0];

	fclose(fin);
}

double det4(double x1, double y1, double x2, double y2) {
	return x1 * y2 - x2 * y1;
}

int sign(double x) {
	if (fabs(x) < eps) return 0;
	if (x < 0.) return -1;
	return 1;
}

void dreapta(coor p1, coor p2, double &a, double &b, double &c) {
	a = p1.y - p2.y;
	b = p2.x - p1.x;
	c = p1.x * p2.y - p2.x * p1.y;
}

int good(coor p1, coor p2, coor p3) {
	return sign( det4(p2.x - p1.x, p2.y - p1.y, p3.x - p1.x, p3.y - p1.y) );
}

coor intersect(coor p1, coor p2, coor p3, coor p4) {
	double a1, b1, c1, a2, b2, c2, d;
	coor R;

	dreapta(p1, p2, a1, b1, c1);
	dreapta(p3, p4, a2, b2, c2);

//	printf("%lf %lf %lf\n", a1, b1, c1);
//	printf("%lf %lf %lf\n", a2, b2, c2);

	d = det4(a1, b1, a2, b2);

	R.x = det4(-c1, b1, -c2, b2) / d;
	R.y = det4(a1, -c1, a2, -c2) / d;

	return R;
}

double arie(int NP, coor P[]) {
	int i;
	double rez = 0.;

	for (i = 0; i < NP; ++i)
		rez += det4(P[i].x, P[i].y, P[i + 1].x, P[i + 1].y);
	
	return rez;
}

void kernel(void) {
	int i, j, a, b, sg;

	NP = 4;
	P[0].x = P[0].y = P[1].x = P[3].y = - VMAX;
	P[1].y = P[3].x = P[2].x = P[2].y = VMAX;

	P[NP] = P[0];

	sg = -sign(arie(N, A));
//	printf("sg %d\n", sg);

	for (i = 0; i < N; ++i) {

		ND = 0;
		for (j = 0; j < NP; ++j) {
			a = good(A[i], A[i + 1], P[j]);
			b = good(A[i], A[i + 1], P[j + 1]);

//			printf("%d %d\n", a, b);

			if (a != sg) D[ND++] = P[j];

			if (a * b == -1)
				D[ND++] = intersect(A[i], A[i + 1], P[j], P[j + 1]);

//			if (b >= 0) D[ND++] = P[j + 1];
		}

		NP = ND;
		memcpy(P, D, (ND + 1) * sizeof(coor));
		P[NP] = P[0];
/*
		for (j = 0; j < NP; ++j)
			printf("(%lf, %lf) ", P[j].x, P[j].y);
		printf("(%lf, %lf)\n", P[NP].x, P[NP].y);
*/
//		return;
	}
}

void write(void) {
	FILE *fout = fopen("camera.out", "wt");
	
	fprintf(fout, "%.2lf\n", 0.5 * fabs( arie(NP, P) ) );

	fclose(fout);
}

int main(void) {

	read();

	kernel();

	write();

	return 0;
}