Cod sursa(job #1494443)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 1 octombrie 2015 09:11:48
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;


constexpr double pi = 3.14159265;
constexpr double eps = 1e-5;

struct segment{
	double a, b, c, phi1, phi2;
	segment(double x1, double y1, double x2, double y2){
		if(x1 > x2){
			swap(x1, x2);
			swap(y1, y2); }
		a = (y1-y2);
		b = (x2-x1);
		c = (a*x1 + b*y1);

		phi1 = atan2(y1, x1);
		phi2 = atan2(y2, x2);
		if(phi1 < 0){
			phi1 += 2*pi; }
		if(phi2 < 0){
			phi2 += 2*pi; }
		if(phi1 > phi2){
			swap(phi1, phi2); }
		if(y1 <= 0 && 0 <= y2 && a != 0 && c/a > 0){
			swap(phi1, phi2); }

		phi1 *= 180, phi2 *= 180;
		phi1 /= pi, phi2 /= pi; }
	void print(){
		cout << a << ' ' << b << ' ' << c << ' ' << (phi1*180/3.14) << ' ' << (phi2*180/3.14) << '\n'; } };

struct eveniment{
	int segment;
	double poz; };

bool operator<(const eveniment& a, const eveniment& b){
	return a.poz < b.poz; }

void fa_sistem(const int n, vector<eveniment>& ev, vector<vector<bool> >& sistem, vector<double>& unghi_var){
	sort(begin(ev), end(ev));
	sistem.resize(n);
	vector<bool> e_atins(n, false);
	int nr_atins = 0;
	double unghi_cur = 0;
	for(const auto e : ev){
		if(nr_atins > 0){
			unghi_var.push_back((unghi_cur+e.poz)/2);
			for(int i = 0; i < n; ++i){
				sistem[i].push_back(e_atins[i]); } }
		unghi_cur = e.poz;
		nr_atins -= e_atins[e.segment];
		e_atins[e.segment] = !e_atins[e.segment];
		nr_atins += e_atins[e.segment]; } }

void solve(vector<vector<bool> >& sist, vector<bool>& rez){
	const int n_ec = sist.size(), n_var = sist[0].size()-1;
	vector<bool> e_rez(n_var, false);
	for(int var = 0, ec = 0; var < n_var && ec < n_ec; ){
		if(!sist[ec][var]){
			int i = ec+1;
			for( ; i < n_ec && !sist[i][var]; ++i);
			if(i < n_ec){
				swap(sist[ec], sist[i]); }
			else{
				++var;
				continue; } }
		for(int i = ec+1; i < n_ec; ++i){
			if(sist[i][var]){
				for(int j = var; j <= n_var; ++j){
					sist[i][j] = (sist[i][j] != sist[ec][j]); } } }
		++var, ++ec; }

	for(int var = n_var-1, ec = n_ec-1; ec >= 0 && var >= 0; --ec){
		for(var = 0; var < n_var && !sist[ec][var]; ++var);
		if(var == n_var){
			continue; }

		rez[var] = sist[ec][n_var];
		for(int i = var+1; i < n_var; ++i){
			if(!e_rez[i]){
				e_rez[i] = true;
				rez[i] = false; }
			if(sist[ec][i]){
				rez[var] = (rez[var] != rez[i]); } }
		e_rez[var] = true; } }

int main(){
	ifstream f("laser.in");
	ofstream g("laser.out");
	int n;
	f >> n;
	vector<eveniment> ev;
	for(int i = 0; i < n; ++i){
		double x1, y1, x2, y2;
		f >> x1 >> y1 >> x2 >> y2;
		segment s(x1, y1, x2, y2);
		if(s.phi1-eps < s.phi2){
			ev.push_back({i, s.phi1});
			ev.push_back({i, s.phi2}); }
		else{
			ev.push_back({i, s.phi1});
			ev.push_back({i, 360});
			ev.push_back({i, 0});
			ev.push_back({i, s.phi2}); } }
	vector<vector<bool> > sistem;
	vector<double> unghi_var;
	fa_sistem(n, ev, sistem, unghi_var);
	for(int i = 0; i < n; ++i){
		bool b;
		f >> b;
		sistem[i].push_back(b); }

	vector<bool> rez(sistem[0].size());
	solve(sistem, rez);
	
	g << count(begin(rez), end(rez), true) << '\n';
	g << fixed << setprecision(6);
	for(int i = 0; i < rez.size(); ++i){
		if(rez[i]){
			g << unghi_var[i] << '\n'; } }
	return 0; }