Cod sursa(job #2540461)

Utilizator NashikAndrei Feodorov Nashik Data 7 februarie 2020 10:27:58
Problema Rays Scor 0
Compilator cpp-64 Status done
Runda irim_eralumis Marime 3.17 kb
//#include <iostream>
#include <cmath>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("rays.in");
ofstream cout("rays.out");
int f[200005],ff[200005];
int ab(int a){
    if(a>0)
        return a;
    return a*-1;
}
double dist_2(int x,int y,int x1,int y1){
    return ab(x-x1)*ab(x-x1)+ab(y-y1)*ab(y-y1);
}
struct cord{
    int x,y1,y2;
}neg[200005],poz[200005];
bool mysort (pair<double,pair<int,int> > a,pair<double,pair<int,int> > b){
    if(a.first==b.first){
        return a.second.second<b.second.second;
    }
    return a.first<b.first;
}
pair<int,pair<int,int> > soln[400005],solp[400005];
int c1,c2;
#define PI 3.14159265
int main()
{
    int n,x,y1,y2;
    double xx,xxx;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y1>>y2;
        cord punct;
        punct.x=x;
        punct.y1=y1;
        punct.y2=y2;
        if(x<0){
            neg[++c1]=punct;
        }
        else
            poz[++c2]=punct;
    }
    for(int i=1;i<=c1;i++){
        int x1=neg[i].x;
        int y1=neg[i].y1;
        int x2=neg[i].x;
        int y2=neg[i].y2;
        double a=dist_2(x1,y1,0,-1);
        double b=dist_2(0,0,x1,y1);
        double c=1;
        a-=b+c;
        a/=-2*b*c;
        //cout<<a<<" "<<acos(a)*180/PI<<"\n";
        ///soln[i*2-1]=make_pair(acos(a)*180/PI,i);
        xx=acos(a)*180/PI;
        a=dist_2(x2,y2,0,-1);
        b=dist_2(0,0,x2,y2);
        c=1;
        a-=b+c;
        a/=-2*b*c;
        ///soln[i*2]=make_pair(acos(a)*180/PI,i);
        xxx=acos(a)*180/PI;
        if(xx<xxx){
            soln[i*2-1]=make_pair(xx,make_pair(i,1));
            soln[i*2]=make_pair(xxx,make_pair(i,2));
        }
        else{
            soln[i*2-1]=make_pair(xx,make_pair(i,2));
            soln[i*2]=make_pair(xxx,make_pair(i,1));
        }
    }
    sort(soln+1,soln+2*c1+1,mysort);
    int rasp=0;
    for(int i=1;i<=2*c1;i++){
        if(f[soln[i].second.first]==rasp+1){
            rasp++;
        }
        else
            f[soln[i].second.first]=rasp+1;
    }
    //cout<<rasp;
    for(int i=1;i<=c2;i++){
        int x1=poz[i].x;
        int y1=poz[i].y1;
        int x2=poz[i].x;
        int y2=poz[i].y2;
        double a=dist_2(x1,y1,0,-1);
        double b=dist_2(0,0,x1,y1);
        double c=1;
        a-=b+c;
        a/=-2*b*c;
        //cout<<a<<" "<<acos(a)*180/PI<<"\n";
        ///solp[i*2-1]=make_pair(acos(a)*180/PI,i);
        xx=acos(a)*180/PI;
        a=dist_2(x2,y2,0,-1);
        b=dist_2(0,0,x2,y2);
        c=1;
        a-=b+c;
        a/=-2*b*c;
        ///solp[i*2]=make_pair(acos(a)*180/PI,i);
        xxx=acos(a)*180/PI;
        if(xx<xxx){
            solp[i*2-1]=make_pair(xx,make_pair(i,1));
            solp[i*2]=make_pair(xxx,make_pair(i,2));
        }
        else{
            solp[i*2-1]=make_pair(xx,make_pair(i,2));
            solp[i*2]=make_pair(xxx,make_pair(i,1));
        }
    }
    sort(solp+1,solp+2*c2+1,mysort);
    for(int i=1;i<=2*c2;i++){
        if(ff[solp[i].second.first]==rasp+1){
            rasp++;
        }
        else
            ff[solp[i].second.first]=rasp+1;
    }
    cout<<rasp;
    return 0;
}