Pagini recente » Cod sursa (job #3241449) | Cod sursa (job #1643347) | Cod sursa (job #2341498) | Cod sursa (job #391758) | Cod sursa (job #2920849)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("laser.in");
ofstream g ("laser.out");
typedef long double LD;
typedef pair <int, int> PII;
typedef pair <PII, PII> PPIPI;
constexpr long double PI = acos(-1);
constexpr int NMAX = 520;
int N;
PPIPI A[NMAX];
LD Angle (PII P) {
LD rads = atan2(1.0 * P.second, 1.0 * P.first);
LD degrees = rads * 180.0 / PI;
return degrees < 0 ? degrees + 360.0 : degrees;
}
void Read () {
f >> N;
for (int i = 1; i <= N; ++ i ) {
f >> A[i].first.first >> A[i].first.second >> A[i].second.first >> A[i].second.second;
if (Angle(A[i].first) > Angle(A[i].second))
swap(A[i].first, A[i].second);
}
}
int vf = 0;
LD Ang[2*NMAX+5];
int Sz = 0;
LD Value[2*NMAX+5];
void Precompute () {
for (int i = 1; i <= N; ++ i ) {
Ang[++vf] = Angle(A[i].first);
Ang[++vf] = Angle(A[i].second);
}
sort(Ang+1, Ang+vf+1);
vector <LD> Red;
Red.push_back(Ang[1]);
for (int i = 2; i <= vf; ++ i )
if (Ang[i] != Red.back()) Red.push_back(Ang[i]);
for (int i = 1; i < Red.size(); ++ i )
Value[i] = (Red[i-1] + Red[i]) * .5;
Sz = Red.size()-1;
if (Red.size() > 1) {
Value[Red.size()] = (Red[0] + Red.back()) * .5 + 180.0;
if (Value[Red.size()] > 360.0) Value[Red.size()] -= 360.0;
Sz = Red.size();
}
}
bitset <2*NMAX> Eq[NMAX];
void Make_Equations () {
for (int i = 1; i <= N; ++ i ) {
LD low = Angle(A[i].first);
LD high = Angle(A[i].second);
LD diff = high - low;
int state;
f >> state;
Eq[i][Sz+1] = state;
for (int j = 1; j <= Sz; ++ j ) {
Eq[i][j] = 0;
if (diff > 180.0) {
if (Value[j] < low || Value[j] > high)
Eq[i][j] = 1;
}
else {
if (low <= Value[j] && Value[j] <= high)
Eq[i][j] = 1;
}
}
}
}
void Afis () {
for (int i = 1; i <= N; ++ i ) {
for (int j = 1; j <= Sz+1; ++ j )
cerr << Eq[i][j] << " ";
cerr << '\n';
}
}
int P[NMAX];
void Gauss () {
//Afis();
for (int i = 1; i <= N; ++ i ) {
int j = 0;
P[i] = 0;
for (j = 1; j <= Sz + 1; ++ j )
if (Eq[i][j]) break;
if (j == Sz+2) continue;
P[i] = j;
for (int j = 1; j <= N; ++ j )
if (i != j && Eq[j][P[i]])
Eq[j] ^= Eq[i];
}
}
void Write () {
//for (int i = 1; i <= N; ++ i )
// cerr << P[i] << " ";
vector <int> ans;
for (int i = 1; i <= N; ++ i ) {
if (P[i] != 0 && Eq[i][Sz+1])
ans.push_back(P[i]);
}
g << ans.size() << '\n';
g << setprecision(6) << fixed;
for (auto it : ans)
g << Value[it] << '\n';
}
int main () {
Read();
Precompute();
Make_Equations();
Gauss();
Write();
return 0;
}