Pagini recente » Cod sursa (job #899013) | Cod sursa (job #3290559) | Cod sursa (job #1073795) | Cod sursa (job #1167578) | Cod sursa (job #2920842)
#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 long double PI = acos(-1);
constexpr int NMAX = 520;
int N;
PPIPI A[NMAX];
long double Angle (PII P) {
long double rads = atan2(P.second, P.first);
long 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;
long double Value[2*NMAX];
bitset <2*NMAX> Eq[NMAX];
void Precompute () {
vector <long 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());
Sz = 0;
for (int i = 0; i < Ang.size() - 1; ++ i ) {
if (Ang[i] != Ang[i+1])
Value[++ Sz] = (Ang[i] + Ang[i+1]) * .5;
}
Value[++ Sz] = (Ang[0] + Ang[Ang.size()-1]) *.5;
Value[Sz] += 180;
if (Value[Sz] > 360.0) Value[Sz] -= 360.0;
for (int i = 1; i <= N; ++ i ) {
long double low = Angle(A[i].first);
long double high = Angle(A[i].second);
long 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;
}