Cod sursa(job #2921328)

Utilizator lolismekAlex Jerpelea lolismek Data 30 august 2022 12:26:12
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("laser.in");
ofstream fout("laser.out");

const int N = 2000;
const double eps = 1e-8, PI = 3.14159265;
vector <double> angles, b;

pair <double, double> interv[N + 1];
bool coef[N + 1][N + 1];
int poz[N + 1];

bool notNull(double x){
	return (x < -eps || x > eps);
}

double angle(double x, double y){
	double ans = atan2(y, x);
	ans += 2 * PI * (ans < 0);
	return ans;
}

int main(){

	int n;
	fin >> n;

	for(int i = 1; i <= n; i++){
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;

		int u1 = angle(x1, y1);
		int u2 = angle(x2, y2);

		angles.push_back(u1);
		angles.push_back(u2);

		if(u1 - u2 > eps)
			swap(u1, u2);

		interv[i] = {u1, u2};
	}

	sort(angles.begin(), angles.end());

	for(int i = 0; i < (int)angles.size() - 1; i++)
		b.push_back((angles[i] + angles[i + 1]) / 2);
	b.push_back((angles[(int)angles.size() - 1] + angles[0] + 2 * PI) / 2);
	if(b[(int)b.size() - 1] > 2 * PI)
		b[(int)b.size() - 1] -= 2 * PI;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= (int)angles.size(); j++){
			bool ok = false;
			if(interv[i].second - interv[i].first > PI)
				ok = ((angles[j - 1] < interv[i].first + eps) || (angles[j - 1] > interv[i].second - eps));
			else
				ok = ((angles[j - 1] - interv[i].first > -eps) && (interv[i].second - angles[j - 1] > -eps));

			coef[i][j] = ok;
		}

	for(int i = 1; i <= n; i++){
		bool touch;
		fin >> touch, coef[i][(int)angles.size() + 1] = touch;
	}

	for(int i = 1; i <= n; i++){
		int j;
		for(j = 1; j <= (int)angles.size() + 1; j++)
			if(coef[i][j])
				break;

		if(j != (int)angles.size() + 2){
			poz[i] = j;
			for(int ind = 1; ind <= n; ind++)
				if(ind != i && coef[ind][poz[i]] != 0)
					for(int jj = 1; jj <= (int)angles.size() + 1; jj++)
						coef[ind][jj] ^= coef[i][jj];
		}
	}
		
	vector <double> sol;
	for(int i = 1; i <= n; i++)
		if(poz[i] && coef[i][(int)angles.size() + 1])
			sol.push_back(b[poz[i] - 1]);

	fout << (int)sol.size() << '\n';

	fout << fixed << setprecision(6);

	for(int i = 0; i < (int)sol.size(); i++)
		fout << sol[i] / PI * 180 << '\n';

	return 0;
}