Cod sursa(job #2540631)

Utilizator cyg_SerbanBFlorin Gheorghe cyg_SerbanB Data 7 februarie 2020 13:21:35
Problema Rays Scor 70
Compilator cpp-64 Status done
Runda irim_eralumis Marime 1.7 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;
struct POINT
{
    long long x,y;
    int i;
};
vector<POINT> st;
vector<POINT> dr;
set<int> s1;
set<int> s2;
bool f[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(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);
    for(int i=0;i<dr.size();++i)
    {
        if(f[dr[i].i])
        {
            if(s1.find(dr[i].i)==s1.end())
                continue;
            s1.clear();
            ans++;
        }
        else
            s1.insert(dr[i].i),f[dr[i].i]=1;
    }
    for(int i=0;i<st.size();++i)
    {
        if(f[st[i].i])
        {
            if(s2.find(st[i].i)==s2.end())
                continue;
            s2.clear();
            ans++;
        }
        else
            s2.insert(st[i].i),f[st[i].i]=1;
    }
    printf("%lld",ans);
    return 0;
}