Cod sursa(job #1767286)

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

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

pair<llt, llt> pnt[2*NMax+1];
pair<int, int> gr[NMax+1];

int nrm[2*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 cmp( pair<llt, llt> A, pair<llt, llt> B )
{
    return A.first*B.second>A.second*B.first;
}

bool cmp2( pair<int, int> A, pair<int, int> B )
{
    if( A.first==B.first ) return A.second<B.second;
    return A.first<B.first;
}

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

void Solve(seg *X, int nt, int l)
{
    int i,j,t,minn,maxx,mint,o,nr,st,dr,mid,f,x,y;

    nr = t = 0;
    for(i = 1; i <= nt; ++i)
    {
        pnt[++t] = mp(X[i].x, X[i].y1);
        pnt[++t] = mp(X[i].x, X[i].y2);
    }

    sort(pnt+1,pnt+t+1,cmp);
    for(o = i = 1; i <= t; ++o)
    {
        for(j = i; pnt[i].first*pnt[j].second==pnt[i].second*pnt[j].first && j <= t; ++j) nrm[j] = o;
        i = j;
    }

    for(i = 1; i <= nt; ++i)
    {
        x = X[i].x;
        y = X[i].y2;
        for(st = 1, dr = t; st <= dr; )
        {
            mid = (st+dr)/2;
            if( x*pnt[mid].second > y*pnt[mid].first ) dr = mid-1;
            else if( x*pnt[mid].second < y*pnt[mid].first ) st = mid+1;
            else { f = mid; break; }
        }
        gr[i].first = f;

        y = X[i].y1;
        for(st = 1, dr = t; st <= dr; )
        {
            mid = (st+dr)/2;
            if( x*pnt[mid].second > y*pnt[mid].first ) dr = mid-1;
            else if( x*pnt[mid].second < y*pnt[mid].first ) st = mid+1;
            else { f = mid; break; }
        }
        gr[i].second = f;
    }

    if(l)
        for(i = 1; i <= nt; ++i) swap( gr[i].first, gr[i].second );

    sort(gr+1,gr+nt+1,cmp2);
    nr = (nt > 0);
    minn = gr[1].first;
    maxx = gr[1].second;
    for(i = 2; i <= nt; ++i)
    {
        if( gr[i].first > minn ) minn = gr[i].first;
        if( gr[i].second < maxx ) maxx = gr[i].second;

        if( minn > maxx )
        {
            minn = gr[i].first;
            maxx = gr[i].second;
            ++nr;
        }
    }

    ans = ans + nr;
}

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(st,nl,0);
    Solve(dr,nr,1);

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



return 0;
}