Pagini recente » Cod sursa (job #2748379) | Cod sursa (job #1868320) | Cod sursa (job #2090566) | Cod sursa (job #2707722) | Cod sursa (job #2920836)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("laser.in");
ofstream g ("laser.out");
typedef pair <int, int> PII;
typedef pair <PII, PII> PPIPI;
constexpr double PI = acos(-1);
constexpr int NMAX = 513;
int N;
PPIPI A[NMAX];
double Angle (PII P) {
double rads = atan2(P.second, P.first);
double 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 Sz;
double Value[2*NMAX];
bitset <2*NMAX> Eq[NMAX];
void Precompute () {
vector <double> Ang;
for (int i = 1; i <= N; ++ i ) {
Ang.push_back(Angle(A[i].first));
Ang.push_back(Angle(A[i].second));
}
sort(Ang.begin(), Ang.end());
for (int i = 0; i < Ang.size() - 1; ++ i )
Value[i+1] = (Ang[i] + Ang[i+1]) * .5;
Value[Ang.size()] = (Ang[0] + Ang[Ang.size()-1]) * .5;
Value[Ang.size()] -= 180;
if (Value[Ang.size()] < 0) Value[Ang.size()] += 360;
Sz = Ang.size();
for (int i = 1; i <= N; ++ i ) {
double low = Angle(A[i].first);
double high = Angle(A[i].second);
double diff = high - low;
bool state;
f >> state;
Eq[i][Sz+1] = state;
for (int j = 1; j <= Sz; ++ j ) {
if (diff < 180) {
if (low <= Value[j] && Value[j] <= high)
Eq[i][j] = 1;
}
else {
if (Value[j] <= low || Value[j] >= high)
Eq[i][j] = 1;
}
}
}
}
int P[NMAX];
void Gauss () {
for (int i = 1; i <= N; ++ i ) {
int j = 0;
P[i] = 0;
for (j = 1; j <= Sz + 1; ++ j )
if (Eq[i][j] == 1) break;
if (j == Sz+2) continue;
if (j == Sz+1) {
cerr << "Wtf ? ";
exit(0);
}
P[i] = j;
for (int j = 1; j <= N; ++ j ) {
if (i != j && Eq[j][P[i]] == 1)
Eq[j] ^= Eq[i];
}
}
}
bool used[NMAX];
void Solve () {
vector <int> ans;
for (int i = 1; i <= N; ++ i )
if (P[i] != 0 && Eq[i][Sz+1] == 1) used[P[i]] = true;
for (int i = 1; i <= Sz; ++ i )
if (used[i]) ans.push_back(i);
g << ans.size() << '\n';
g << setprecision(6) << fixed;
for (auto it : ans)
g << Value[it] << '\n';
}
int main () {
Read();
Precompute();
Gauss();
Solve();
return 0;
}