Pagini recente » Cod sursa (job #187776) | Statistici David Antonio (MixiStorm) | Cod sursa (job #2785331) | Cod sursa (job #2018736) | Cod sursa (job #2592040)
#include <bits/stdc++.h>
using namespace std;
ifstream f("laser.in");
ofstream g("laser.out");
typedef pair < int, int > PII;
typedef pair < PII, PII > Segment;
const int NMAX = (1 << 9) + 5;
const long double DOI = 2.000000, PI = acos(-1), Q = 180.000000;
int N;
bool State[NMAX];
Segment A[NMAX];
int M = 0;
PII Points[(NMAX << 1)];
int v = 0;
long double V[(NMAX << 1)];
vector < long double > Bisect;
bitset < (NMAX << 1) > G[NMAX];
int Equations = 0, Variables = 0;
int Chosen[NMAX];
bool fr[(NMAX << 1)];
static inline long double GetAngle (int X, int Y)
{
long double x = X, y = Y;
long double ans = atan2(y, x);
if(y < 0)
ans += DOI * PI;
return (ans * (Q / PI));
}
static inline void Read ()
{
f.tie(NULL);
f >> N;
for(int i = 1; i <= N; ++i)
{
int X1 = 0, Y1 = 0, X2 = 0, Y2 = 0;
f >> X1 >> Y1 >> X2 >> Y2;
if(GetAngle(X1, Y1) > GetAngle(X2, Y2))
swap(X1, X2), swap(Y1, Y2);
A[i] = {{X1, Y1}, {X2, Y2}};
Points[++M] = {X1, Y1};
Points[++M] = {X2, Y2};
}
Equations = N;
return;
}
auto cmp = [] (PII A, PII B)
{
if(GetAngle(A.first, A.second) < GetAngle(B.first, B.second))
return 1;
return 0;
};
static inline void Build ()
{
sort(Points + 1, Points + M + 1, cmp);
V[++v] = GetAngle(Points[1].first, Points[1].second);
for(int i = 2; i <= M; ++i)
{
long double Now = GetAngle(Points[i].first, Points[i].second);
if(Now == V[v])
continue;
V[++v] = Now;
}
for(int i = 1; i < v; ++i)
Bisect.push_back((V[i] + V[i + 1]) / DOI);
if(v > 1)
{
Bisect.push_back((V[1] + V[v] + DOI * Q) / DOI);
if(Bisect.back() > (DOI * Q))
Bisect.back() -= (DOI * Q);
}
Variables = (int)Bisect.size();
for(int i = 1; i <= N; ++i)
{
f >> State[i];
G[i][Variables + 1] = State[i];
}
return;
}
static inline void Continue ()
{
for(int i = 1; i <= N; ++i)
{
long double Min = GetAngle(A[i].first.first, A[i].first.second);
long double Max = GetAngle(A[i].second.first, A[i].second.second);
long double Delta = Max - Min;
bool Val = 0;
if(Delta > Q)
Val = 1;
for(int j = 0; j < Variables; ++j)
{
long double Angle = Bisect[j];
int Bool = 0;
if(Val == 0)
{
if(Angle >= Min && Angle <= Max)
Bool = 1;
}
else
{
if(Angle < Min || Angle > Max)
Bool = 1;
}
G[i][j + 1] = Bool;
}
}
return;
}
static inline void GaussianElimination ()
{
for(int i = 1; i <= Equations; ++i)
{
int pos = 0;
for(int j = 1; j <= Variables + 1; ++j)
if(G[i][j])
{
pos = j;
break;
}
if(pos == 0)
continue;
Chosen[i] = pos;
for(int j = 1; j <= Equations; ++j)
if(i != j && G[j][pos])
G[j] ^= G[i];
}
return;
}
static inline void Write ()
{
int r = 0;
for(int i = 1; i <= Equations; ++i)
if(Chosen[i] && G[i][Variables + 1])
fr[Chosen[i]] = 1, ++r;
g << r << '\n';
g << setprecision(6) << fixed;
for(int i = 1; i <= Variables; ++i)
if(fr[i])
g << Bisect[i - 1] << '\n';
return;
}
int main()
{
Read();
Build();
Continue();
GaussianElimination();
Write();
return 0;
}