Cod sursa(job #2540533)

Utilizator NashikAndrei Feodorov Nashik Data 7 februarie 2020 12:18:28
Problema Rays Scor 60
Compilator cpp-64 Status done
Runda irim_eralumis Marime 4.86 kb
//#include <iostream>
#include <cmath>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("rays.in");
ofstream cout("rays.out");
bool f[200005],ff[200005];
long long ab(int a){
    if(a>0)
        return a;
    return a*-1;
}
long long dist_2(int x,int y,int x1,int y1){
    long long r=ab(x-x1),p=ab(y-y1);
    r*=r;
    p*=p;
    r+=p;
    return r;
}
struct cord{
    int x,y1,y2;
}neg[200005],poz[200005];
int cur[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<double,pair<int,int> > soln[400005],solp[400005];
int c1,c2,contor;
#define PI 3.14159265
int main()
{
    ios::sync_with_stdio(false);
    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{
            punct.x*=-1;
            poz[++c2]=punct;
        }
    }
    double pp;
    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;
        //cout<<a<<" "<<b<<" "<<c<<"\n";
        a-=b+c;
        pp=(double)sqrt(b)*-2;
        a/=pp;
        //cout<<a<<" "<<acos(a)*180.0/PI<<"\n";
        ///soln[i*2-1]=make_pair(acos(a)*180.0/PI,i);
        xx=acos(a)*180.0/PI;
        a=dist_2(x2,y2,0,-1);
        b=dist_2(0,0,x2,y2);
        c=1;
        a-=b+c;
        pp=(double)sqrt(b)*-2;
        a/=pp;
        ///soln[i*2]=make_pair(acos(a)*180.0/PI,i);
        xxx=acos(a)*180.0/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);
    //for(int i=1;i<=2*c1;i++){
    //    cout<<soln[i].first<<" "<<soln[i].second.first<<" "<<soln[i].second.second<<"\n";
    //}
    //cout<<"\n\n";
    int rasp=0;
    for(int i=1;i<=2*c1;i++){
        if(f[soln[i].second.first]==1){
            continue;
        }
        else{
            if(f[soln[i].second.first]==0){
                if(soln[i].second.second==1){
                    cur[++contor]=soln[i].second.first;
                }
                else{
                    rasp++;
                    while(contor!=0){
                        f[cur[contor]]=1;
                        contor--;
                    }
                }
            }
        }
    }
    //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;
        pp=(double)sqrt(b)*-2;
        a/=pp;
        //cout<<a<<" "<<acos(a)*180.0/PI<<"\n";
        ///solp[i*2-1]=make_pair(acos(a)*180.0/PI,i);
        xx=acos(a)*180.0/PI;
        a=dist_2(x2,y2,0,-1);
        b=dist_2(0,0,x2,y2);
        c=1;
        a-=b+c;
        pp=(double)sqrt(b)*-2;
        a/=pp;
        ///solp[i*2]=make_pair(acos(a)*180.0/PI,i);
        xxx=acos(a)*180.0/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*c1;i++){
        //cout<<solp[i].first<<" "<<solp[i].second.first<<" "<<solp[i].second.second<<"\n";
    //}
    //cout<<"\n\n";
    for(int i=1;i<=2*c2;i++){
        if(ff[solp[i].second.first]==1){
            continue;
        }
        else{
            if(ff[solp[i].second.first]==0){
                if(solp[i].second.second==1){
                    cur[++contor]=solp[i].second.first;
                }
                else{
                    rasp++;
                    while(contor!=0){
                        ff[cur[contor]]=1;
                        contor--;
                    }
                }
            }
        }
    }
    cout<<rasp;
    return 0;
}
/**
12
-3 1 1
-6 2 2
-9 3 3
-12 4 4
-15 5 5
-18 6 6

3 1 1
6 2 2
9 3 3
12 4 4
15 5 5
18 6 6

6
-1000000000 1000000000 1000000000
-999999999 999999999 999999999
-999999998 999999998 999999998
-3 3 3
2 2 2
1000000000 1000000000 1000000000

10
2 2 2
2 45 45
56 45 12
-21 12 1 2
1 1
1
 1
1
1
1
1
1
1
1
11
1
1
1
1
11
*/