Pagini recente » Cod sursa (job #1513484) | Cod sursa (job #1712289) | Cod sursa (job #3120397) | Cod sursa (job #2287048) | Cod sursa (job #1494450)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
constexpr double pi = 3.14159265;
constexpr double eps = 1e-5;
struct segment{
double phi1, phi2;
segment(double x1, double y1, double x2, double y2){
phi1 = atan2(y1, x1);
phi2 = atan2(y2, x2);
if(phi1 < 0){
phi1 += 2*pi; }
if(phi2 < 0){
phi2 += 2*pi; }
if(phi1 > phi2){
swap(phi1, phi2); }
if(phi2 - phi1 > 180){
swap(phi1, phi2); }
phi1 *= 180, phi2 *= 180;
phi1 /= pi, phi2 /= pi; } };
struct eveniment{
int segment;
double poz; };
bool operator<(const eveniment& a, const eveniment& b){
return a.poz < b.poz; }
void fa_sistem(const int n, vector<eveniment>& ev, vector<vector<bool> >& sistem, vector<double>& unghi_var){
sort(begin(ev), end(ev));
sistem.resize(n);
vector<bool> e_atins(n, false);
int nr_atins = 0;
double unghi_cur = 0;
for(const auto e : ev){
if(nr_atins > 0 && e.poz - unghi_cur > eps){
unghi_var.push_back((unghi_cur+e.poz)/2);
for(int i = 0; i < n; ++i){
sistem[i].push_back(e_atins[i]); } }
unghi_cur = e.poz;
nr_atins -= e_atins[e.segment];
e_atins[e.segment] = !e_atins[e.segment];
nr_atins += e_atins[e.segment]; } }
void solve(vector<vector<bool> >& sist, vector<bool>& rez){
const int n_ec = sist.size(), n_var = sist[0].size()-1;
vector<bool> e_rez(n_var, false);
for(int var = 0, ec = 0; var < n_var && ec < n_ec; ){
if(!sist[ec][var]){
int i = ec+1;
for( ; i < n_ec && !sist[i][var]; ++i);
if(i < n_ec){
swap(sist[ec], sist[i]); }
else{
++var;
continue; } }
for(int i = ec+1; i < n_ec; ++i){
if(sist[i][var]){
for(int j = var; j <= n_var; ++j){
sist[i][j] = (sist[i][j] != sist[ec][j]); } } }
++var, ++ec; }
for(int var = n_var-1, ec = n_ec-1; ec >= 0 && var >= 0; --ec){
for(var = 0; var < n_var && !sist[ec][var]; ++var);
if(var == n_var){
continue; }
rez[var] = sist[ec][n_var];
for(int i = var+1; i < n_var; ++i){
if(!e_rez[i]){
e_rez[i] = true;
rez[i] = false; }
if(sist[ec][i] && rez[i]){
rez[var] = !rez[var]; } }
e_rez[var] = true; } }
int main(){
ifstream f("laser.in");
ofstream g("laser.out");
int n;
f >> n;
vector<eveniment> ev;
for(int i = 0; i < n; ++i){
double x1, y1, x2, y2;
f >> x1 >> y1 >> x2 >> y2;
segment s(x1, y1, x2, y2);
if(s.phi1-eps < s.phi2){
ev.push_back({i, s.phi1});
ev.push_back({i, s.phi2}); }
else{
ev.push_back({i, s.phi1});
ev.push_back({i, 360});
ev.push_back({i, 0});
ev.push_back({i, s.phi2}); } }
vector<vector<bool> > sistem;
vector<double> unghi_var;
fa_sistem(n, ev, sistem, unghi_var);
for(int i = 0; i < n; ++i){
bool b;
f >> b;
sistem[i].push_back(b); }
vector<bool> rez(sistem[0].size());
solve(sistem, rez);
g << count(begin(rez), end(rez), true) << '\n';
g << fixed << setprecision(6);
for(int i = 0; i < rez.size(); ++i){
if(rez[i]){
g << unghi_var[i] << '\n'; } }
return 0; }