Cod sursa(job #37991)

Utilizator eferLiviu Ciortea efer Data 25 martie 2007 13:14:11
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.47 kb
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <utility>
#include <string>
using namespace std;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define REPV(i, a, b) for (int i = (a); i <= (b); ++i)
#define REPD(i, N) for (int i = (N)-1; i >= 0; --i)
#define REPVD(i, b, a) for (int i = (b); i >= (a); --i)
#define REPIT(it, v) for (it = (v).begin(); it != (v).end(); ++it)
#define SZ(a) ((int)(a).size())
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define ALL(a) (a).begin(), (a).end()
#define CLR(a) memset((a), 0, sizeof(a))
#define MSET(a, v) memset((a), v, sizeof(a))
#define CPY(dest, source) memcpy(dest, source, sizeof(dest))

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef set<int> SI;
typedef map<int, int> MII;
typedef deque<int> QI;
typedef deque<PII> QPII;

const int MAXN = 1024;

struct evnt {
	int c, ind, type;
	double angle;
	evnt() {}
	evnt(int n, int m, int p, double a): c(n), ind(m), type(p), angle(a) {};
} E[2*MAXN];
bool operator < (const evnt& a, const evnt& b) {
	if (a.c != b.c) return a.c < b.c;
	return a.type < b.type;
}

struct seg {
	int x1, y1, x2, y2, cs, cd;
	double a1, a2;
	seg() { cd = cd = -1; }
} S[MAXN];

struct point {
	int x, y, ind;
	double angle;
	point() {}
	point(int xx, int yy, int i): x(xx), y(yy), ind(i) {
		angle = atan2(1.0 * y, 1.0 * x);
	}
} P[3*MAXN];
bool operator < (const point& a, const point& b) {
	return a.angle < b.angle;
}

int N, state[MAXN];
PII ints[MAXN];
VI sol;

inline int between(int a, int b, int c) {
	return (a < c && c <= b) || (a > b && (a < c || c <= b));
}

int solve() {
	sort(E, E+2*N);

	//REP(i, 2*N) cerr<<E[i].c<<" ";
	//cerr<<endl;

	int res = 10001;

	REP(i, 2*N) {
	//REPV(i, 1, 1) {
		sol.clear();

		set<int> on, off, gon, goff;
		REP(j, N) {
			if (between(ints[j].X, ints[j].Y, E[i].c)) {
				//cerr<<j<<" "<<state[j]<<endl;
				if (state[j]) on.insert(j);
				else off.insert(j);
			} else {
				if (state[j]) gon.insert(j);
				else goff.insert(j);
			}
		}

		int j = i, shoot = 0;
		do {
			//cerr<<j<<" "<<E[j].type<<" "<<E[j].ind<<endl;
			if (E[j].type == 0) {
				if (gon.find(E[j].ind) != gon.end()) {
					//cerr<<"put on"<<endl;
					gon.erase(E[j].ind);
					on.insert(E[j].ind);
				} else {
					//cerr<<"put off"<<endl;
					goff.erase(E[j].ind);
					off.insert(E[j].ind);
				}
			} else {
				if (on.find(E[j].ind) != on.end()) {
					on.erase(E[j].ind);
					gon.insert(E[j].ind);
				} else {
					off.erase(E[j].ind);
					goff.insert(E[j].ind);
				}
			}

			if (!on.empty()) {
				//cerr<<"shoot "<<E[j].c<<" "<<*(on.begin())<<endl;
				shoot++;
				swap(on, off);
				sol.PB(j);
			}

			j = (j + 1) % (2 * N);
		} while (j != i);

		if (on.empty() && gon.empty()) {
			res = shoot;
			break;
		}
	}

	return res;
}

void process() {
	sort(P, P+3*N);
	REP(i, 3*N) {
		if ((P[i].ind & 1) == 0) {
			int ind = P[i].ind>>1;
			//cerr<<i<<" "<<ind<<endl;
			if (S[ind].cs == -1) S[ind].cs = i, S[ind].a1 = P[i].angle;
			else S[ind].cd = i, S[ind].a2 = P[i].angle;
		}
	}

	REP(i, 3*N) {
		if (P[i].ind & 1) {
			int ind = P[i].ind>>1;
			if (!between(S[ind].cs, S[ind].cd, i)) {
				swap(S[ind].cs, S[ind].cd);
				swap(S[ind].a1, S[ind].a2);
			}
		}
	}
}

const double PI = 2 * acos(0.0);

inline double todeg(double angle) {
	if (angle < 0.0) angle += 2 * PI;
	return angle / PI * 360.0;
}

int main() {
	freopen("laser.in", "rt", stdin);
	freopen("laser.out", "wt", stdout);

	scanf("%d", &N);
	REP(i, N) {
		S[i].cs = S[i].cd = -1;
		scanf("%d %d %d %d", &S[i].x1, &S[i].y1, &S[i].x2, &S[i].y2);
		P[3*i] = point(S[i].x1<<1, S[i].y1<<1, i<<1);
		P[3*i+1] = point(S[i].x2<<1, S[i].y2<<1, i<<1);
		P[3*i+2] = point(S[i].x1+S[i].x2, S[i].y1+S[i].y2, (i<<1)|1);
	}

	process();

	REP(i, N) {
		int cs = S[i].cs, cd = S[i].cd;
		fprintf(stderr, "seg %d: %d %d\n", i, cs, cd);
		E[i<<1] = evnt(cs, i, 0, S[i].a1);
		E[(i<<1)|1] = evnt(cd, i, 1, S[i].a2);
		ints[i] = MP(cs, cd);
	}

	REP(i, N) scanf("%d", &state[i]);

	int res = solve();
	printf("%d\n", res);

	REP(i, SZ(sol)) {
		printf("%0.6lf\n", todeg(0.5 * (E[sol[i]].angle + E[(sol[i]+1)%(2*N)].angle)));
	}

	return 0;
}