Cod sursa(job #2556067)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 24 februarie 2020 17:41:07
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("rays.in");
ofstream fout("rays.out");

#define PI 3.14159265359

int n;

struct lol{
  double a;
  int tip;
  int id;
  bool operator<(lol x){
    return a<x.a||(a==x.a&&tip<x.tip);
  }
};

vector<lol> v;

int main()
{
  fin>>n;
  int id=0;
  bool vis[2*n+2];
  memset(vis, 0, sizeof vis);
  for(int i=1;i<=n;++i){
    int x, y1, y2;
    fin>>x>>y1>>y2;
    double a=atan2(x, -y1);
    if(a<0) a=2*PI+a;
    double b=atan2(x, -y2);
    if(b<0) b=2*PI+b;
    if(a>b) swap(a, b);
    v.push_back({a, 0, ++id});
    v.push_back({b, 1, id});
  }
  sort(v.begin(), v.end());
  int nr=0;
  stack<int> todel;
  for(auto i:v){
    if(vis[i.id]==0){
      if(i.tip==0){
        todel.push(i.id);
      }
      else{
        nr++;
        while(!todel.empty()){
          vis[todel.top()]=1;
          todel.pop();
        }
      }
    }
  }
  fout<<nr<<"\n";
  return 0;
}