Cod sursa(job #1730797)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 17 iulie 2016 17:01:51
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 520;

#define Point pair<double, double>

struct Segment {

	Point a;
	Point b;
	Segment(double x1, double y1, double x2, double y2) {

		a.first = x1; a.second = y1;
		b.first = x2; b.second = y2;
	}
};

int n;//nr ecuatii aka neoane 
int m;//nr necunoscute, aka lasere

bool a[NMAX][NMAX * 2];
 //a[i][j] = 1 daca neonul i isi schimba starea prin aprinderea laserului j

bool sol[NMAX * 2];//starea unui laser

vector<Segment> seg;
vector<Point> points;
vector<Point> lasers;

void read() {

	fin >> n;

	for(int i = 1; i <= n; ++i) {

		double x1, x2, y1, y2;
		fin >> x1 >> y1 >> x2 >> y2;
		seg.push_back({x1, y1, x2, y2});
		points.push_back({x1, y1});
		points.push_back({x2, y2});
	}
}


double getDegrees(Point p) {

	double u = atan2(p.second, p.first);

	double d = u * (180 / M_PI);

	if(u < 0) return d + 360;
	return d;
}

struct cmp {

	bool operator() (const Point& p1, const Point& p2) {

		double u1 = atan2(p1.second , p1.first); //[-pi, pi]
		double u2 = atan2(p2.second , p2.first); 

		double degu1 = (u1 + M_PI) * (180 / M_PI);
		double degu2 = (u2 + M_PI) * (180 / M_PI);

		return degu1 < degu2;
	}

} cmp1 ;

double modulo(double x) { return x > 0 ? x : -x; }

bool intersects(Point p1, Point p2, Point p3) {

	double u1 = atan2(p1.second , p1.first);
	double u2 = atan2(p2.second , p2.first);
	double u3 = atan2(p3.second , p3.first);

	double degu1 = (u1 + M_PI) * (180 / M_PI);
	double degu2 = (u2 + M_PI) * (180 / M_PI);
	double degu3 = (u3 + M_PI) * (180 / M_PI);

	bool inter = (degu1 <= degu3 && degu3 <= degu2) ||
			(degu2 <= degu3 && degu3 <= degu1);

	if(modulo(degu1 - degu2) <= 180) 
		return inter;
			else 
		return !inter;

}

void constructMatrix() {

	for(int i = 1; i <= n ; ++i)
		fin >> a[i][m + 1];

	for(int i = 1; i <= n; ++i) {//segemnt aka ecuatie
		
		Segment s = seg[i - 1];
		for(int j = 1; j <= m ; ++j) {//laser aka necunoscuta
			//segemntul s intereseacteaza laserele cu unghiul: dat de punctul
			Point p = points[j - 1];
			if(intersects(s.a, s.b, p))
				a[i][j] = true;

		}
	}
}

void gauss() {

	int i = 1; int j = 1;

	while(i <= n && j <= m) {

		//caut element nenul pe coloana j
		int x = i;
		for( ; x <= n ; ++x)
			if(a[x][j])
				break;
		if(x == n + 1) //variabila libera
			sol[j] = false;
		//interschimb linia i cu linia x
		for(int c = j ; c <= m + 1; c++)
			swap(a[x][c], a[x][i]);

		//fac zerouri sub linia i
		for(x = i + 1; x <= n ; ++x)
			if(a[x][j])
				for(int c = j ; c <= m + 1; c++)
					a[x][c] = a[x][c] xor a[i][c];
		i++; j++;
	}

	for(i = n; i ; --i) {

		for(j = 1; j <= m + 1; ++j) {

			if(a[i][j] == true) 
				break;
		}

		if(j == m + 1) {
			cout << "Imposibil\n";
			exit(0);
		}

		sol[j] = a[i][m + 1];

		for(int c = j + 1; c <= m ; ++c)
			sol[j] = sol[j] xor (sol[c] and a[i][c]);	
	}
}


void solve() {

	sort(points.begin(), points.end(), cmp1);
	points.push_back(points[0]);

	for(int i = 0 ; i < points.size() - 1; ++i) {
		lasers.push_back({(points[i].first + points[i + 1].first) / 2,
						   (points[i].second + points[i + 1].second) / 2});
	}

	m = lasers.size();

	constructMatrix();
	gauss();


	int cnt = 0;
	for(int i = 1; i <= m; ++i)
		if(sol[i])
			cnt++;

	fout << cnt << '\n'; 

	fout << fixed << setprecision(7) ;

	for(int i = 1; i <= m; ++i)
		if(sol[i])
			fout << getDegrees(lasers[i - 1]) << '\n'; 
}

int main() {

	read();

	solve();

	return 0;
}