Cod sursa(job #2072827)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 22 noiembrie 2017 12:07:23
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>
#include<algorithm>
#include<limits.h>
#define MAXN 200000
struct segment
{
    int x,y1,y2;
};
bool cmp(segment a,segment b);
FILE*fin,*fout;
segment pozitiv[MAXN+1];
segment negativ[MAXN+1];
int ultpoz=-1,ultneg=-1;
int main()
{
    fin=fopen("rays.in","r");
    fout=fopen("rays.out","w");
    int N;
    fscanf(fin,"%d",&N);
    for(int i=1; i<=N; i++)
    {
        int x,y1,y2;
        fscanf(fin,"%d%d%d",&x,&y1,&y2);
        if(y1>y2)
            std::swap(y1,y2);
        if(x<0)
        {
            x=-x;
            negativ[++ultneg].x=x;
            negativ[ultneg].y1=y1;
            negativ[ultneg].y2=y2;
        }
        else
        {
            pozitiv[++ultpoz].x=x;
            pozitiv[ultpoz].y1=y1;
            pozitiv[ultpoz].y2=y2;
        }
    }
    std::sort(negativ,negativ+ultneg+1,cmp);
    std::sort(pozitiv,pozitiv+ultpoz+1,cmp);
    long long ans=0;
    int last=0;
    if(ultneg>=0)
    {
        ans++;
        last=0;
        for(int i=1; i<=ultneg; i++)
        {
            if((1LL)*negativ[last].y2*negativ[i].x<(1LL)*negativ[i].y1*negativ[last].x)
            {
                last=i;
                ans++;
            }
        }
    }
    if(ultpoz>=0)
    {
        ans++;
        last=0;
        for(int i=1; i<=ultpoz; i++)
        {
            if((1LL)*pozitiv[last].y2*pozitiv[i].x<(1LL)*pozitiv[i].y1*pozitiv[last].x)
            {
                last=i;
                ans++;
            }
        }
    }
    fprintf(fout,"%lld",ans);
}
bool cmp(segment a,segment b)
{
    return (1LL)*a.y2*b.x<(1LL)*a.x*b.y2;
}