Cod sursa(job #2540628)

Utilizator cyg_SerbanBFlorin Gheorghe cyg_SerbanB Data 7 februarie 2020 13:10:41
Problema Rays Scor 10
Compilator cpp-64 Status done
Runda irim_eralumis Marime 1.9 kb
//
//  main.cpp
//  delucru-geometrie-analitica
//
//  Created by Serban Bantas on 30/01/2020.
//  Copyright � 2020 Serban Bantas. All rights reserved.
//
#include <bits/stdc++.h>
using namespace std;
const double eps=1.e-14;///10^-14
const double INF=1.e9;///10^9
///INF poate lua valoare maxima 10^237
struct POINT
{
    long long x,y;
    int i;
};
vector<POINT> st;
vector<POINT> dr;
bool f1[200005],f2[200005];
bool cmp(POINT A,POINT B)
{
    long long p1=A.x*B.y,p2=B.x*A.y;
    if(p1==p2)
        return A.i>B.i;
    return p1<p2;
}
int main(int argc, const char * argv[])
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int n;
    long long ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        long long x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        if(y>z)
        swap(y,z);
        if(x>0)
        {
            dr.push_back({x,y,i});
            dr.push_back({x,z,i});
        }
        else
        {
            st.push_back({-x,y,i});
            st.push_back({-x,z,i});
        }
    }
    sort(dr.begin(),dr.end(),cmp);
//    for(int i=0;i<dr.size();++i)
//        printf("%lf %lf %d\n",dr[i].x,dr[i].y,dr[i].c);
    sort(st.begin(),st.end(),cmp);
//    for(int i=0;i<st.size();++i)
//        printf("%lf %lf %d\n",-st[i].x,st[i].y,st[i].c);
    queue<POINT> q;
    for(int i=0;i<dr.size();++i)
    {
        if(f1[dr[i].i])
        {
            if(q.empty())
                continue;
            while(!q.empty())
                q.pop();
            ans++;
        }
        else
            q.push(dr[i]),f1[dr[i].i]=1;
    }
    while(!q.empty())
        q.pop();
    for(int i=0;i<st.size();++i)
    {
        if(f2[st[i].i])
        {
            if(q.empty())
                continue;
            while(!q.empty())
                q.pop();
            ans++;
        }
        else
            q.push(st[i]),f2[st[i].i]=1;
    }
    printf("%lld",ans);
    return 0;
}