Pagini recente » Cod sursa (job #902486) | Cod sursa (job #2555076) | Cod sursa (job #1385805) | Cod sursa (job #123895) | Cod sursa (job #2283179)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const double eps = 0.000001;
const double PI = acos(-1);
struct punct
{
punct(double x = 0, double y = 0)
{
this->x = x;
this->y = y;
}
double x, y;
};
struct segm
{
segm(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0)
{
this->a.x = x1;
this->a.y = y1;
this->b.x = x2;
this->b.y = y2;
}
punct a, b;
bool aprins;
};
inline double degrees(double radians)
{
if(radians < 0)
radians += 2 * PI;
return radians * 180 / PI;
}
inline double GetSlope(const punct &A)
{
return atan2(A.y, A.x);
}
bool intersect(double slope, const segm &s)
{
double minSlope = GetSlope(s.a);
double maxSlope = GetSlope(s.b);
if(maxSlope < minSlope)
swap(minSlope, maxSlope);
bool ret = minSlope <= slope && slope <= maxSlope;
if(maxSlope - minSlope > PI)
return !ret;
return ret;
}
int main()
{
ifstream in("laser.in");
int n;
in >> n;
vector<segm> v(n);
for(auto &s:v)
in >> s.a.x >> s.a.y >> s.b.x >> s.b.y;
for(auto &s:v)
in >> s.aprins;
in.close();
int m = 2*n;
vector<vector<bool> > a(n, vector<bool>(m+1));
vector<double> slopes(m);
for(int i = 0; i < n; ++i)
{
slopes[2*i] = GetSlope(v[i].a);
slopes[2*i+1] = GetSlope(v[i].b);
}
for(int i = 0; i < n; ++i)
{
a[i][m] = v[i].aprins;
for(int j = 0; j < m; ++j)
{
if(j == 2 * i || j == 2 * i + 1)
a[i][j] = 1;
else
a[i][j] = intersect(slopes[j], v[i]);
}
}
for(int i = 0, j = 0; i < n && j < m; ++i, ++j)
{
for(int k = i; k < n; ++k)
{
if(a[k][j] != 0)
{
if(i != k)
swap(a[i], a[k]);
break;
}
}
if(a[i][j] == 0)
{
--i;
continue;
}
for(int k = i+1; k < n; ++k)
{
for(int l = m; l >= j; --l)
a[k][l] = a[k][l] ^ (a[i][l] && a[k][j]);
}
}
vector<bool> rasp(m);
for(int i = n-1; i >= 0; --i)
{
int j;
for(int k = 0; k < m; ++k)
if(a[i][k] != 0)
{
j = k;
break;
}
rasp[j] = a[i][m];
for(int k = j+1; k < m; ++k)
rasp[j] = rasp[j] ^ (a[i][k] && rasp[k]);
}
ofstream out("laser.out");
int trageri = 0;
for(int i = 0; i < m; ++i)
trageri += rasp[i];
out << trageri << "\n";
for(int i = 0; i < m; ++i)
{
if(rasp[i])
out << fixed << setprecision(8) << degrees(slopes[i]) << "\n";
}
return 0;
}