Cod sursa(job #1767388)

Utilizator silkMarin Dragos silk Data 28 septembrie 2016 22:48:43
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <cstdio>
#include <algorithm>
#define NMax 200000
#define mp make_pair
#define DIM 10000
using namespace std;
char buff[DIM];
int poz;

struct seg { int x,y1,y2; };
seg st[NMax+1], dr[NMax+1];

int nr,nl,ans;

void Read(int& numar)
{
    char sgn='+';
    numar = 0;
    while(buff[poz]<'0'||buff[poz]>'9')
    {
        sgn = buff[poz];
        if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
    }
    while(buff[poz]>='0'&&buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if(++poz==DIM) fread(buff,1,DIM,stdin),poz=0;
    }
    if(sgn=='-') numar=-numar;
}

bool cmp1(const seg A, const seg B )
{
    if( 1LL*A.y1*B.x==1LL*A.x*B.y1 ) return 1LL*A.y2*B.x<1LL*A.x*B.y2;
    return 1LL*A.y1*B.x<1LL*A.x*B.y1;
}

bool cmp2(const seg A, const seg B )
{
    if( 1LL*A.x*B.y1==1LL*A.y1*B.x ) return 1LL*A.x*B.y2==1LL*A.y2*B.x;
    return 1LL*A.x*B.y1<1LL*A.y1*B.x;
}

void swap(int& a, int& b)
{
    int aux = a;
    a = b;
    b = aux;
}

void Solve_dr()
{
    int i,j,f,lx,ly,rx,ry;

    if(nr==0) return;

    f = 1;
    sort(dr+1,dr+nr+1,cmp1);
    lx = dr[1].x; ly = dr[1].y1;
    rx = dr[1].x; ry = dr[1].y2;

    for(i = 2; i <= nr; ++i)
    {
        if( 1LL*ly*dr[i].x < 1LL*lx*dr[i].y1 ) { lx = dr[i].x; ly = dr[i].y1; }
        if( 1LL*ry*dr[i].x > 1LL*rx*dr[i].y2 ) { rx = dr[i].x; ry = dr[i].y2; }

        if( 1LL*ly*rx > 1LL*lx*ry )
        {
            lx = dr[i].x; ly = dr[i].y1;
            rx = dr[i].x; ry = dr[i].y2;
            ++f;
        }
    }

    ans = ans + f;
}

void Solve_st()
{
    int i,j,f,lx,ly,rx,ry;

    if(nl==0) return;

    f = 1;
    sort(st+1,st+nl+1,cmp2);
    lx = st[1].x; ly = st[1].y1;
    rx = st[1].x; ry = st[1].y2;

    for(i = 2; i <= nl; ++i)
    {
        if( 1LL*lx*st[i].y1 < 1LL*ly*st[i].x ) { lx = st[i].x; ly = st[i].y1; }
        if( 1LL*rx*st[i].y2 > 1LL*ry*st[i].x ) { rx = st[i].x; ry = st[i].y2; }

        if( 1LL*ly*rx < 1LL*lx*ry )
        {
            lx = st[i].x; ly = st[i].y1;
            rx = st[i].x; ry = st[i].y2;
            ++f;
        }
    }

    ans = ans + f;
}

int main(){
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);

    int i,N,x,y1,y2;

    scanf("%d",&N);
    for(nr = nl = 0, i = 1; i <= N; ++i)
    {
        Read(x);
        Read(y1);
        Read(y2);
        if( y1 > y2 ) swap(y1,y2);

        if(x>0) { dr[++nr].x = x; dr[nr].y1 = y1; dr[nr].y2 = y2; }
        else { st[++nl].x = x; st[nl].y1 = y1; st[nl].y2 = y2; }
    }

    Solve_dr();
    Solve_st();

    printf("%d\n", ans);



return 0;
}