Cod sursa(job #2004022)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 24 iulie 2017 17:41:48
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
///Prima problema de la articolul cu arbori binari in geometrie
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int ai[5003],rasp=0,minY=0x3f3f3f,maxY=-0x3f3f3f;
struct punct
{
    int x,y;
    bool orizontal;
} vCit[1000];
bool cmp(punct p1,punct p2)
{
    if(p1.x==p2.x)
    {
        if(p1.orizontal==p2.orizontal)
            return p1.y<p2.y;
        else
            return p1.orizontal==true;
    }
    return p1.x<p2.x;
}
void actualizare(int poz,int st,int dr,int val)
{
    int mij=(st+dr)/2;
    if(st>=dr)
        {
            ai[poz]=!ai[poz];
            return;
        }
    if(mij>=val)
        actualizare(2*poz,st,mij,val);
    else
        actualizare(2*poz+1,mij+1,dr,val);
    ai[poz]=ai[2*poz]+ai[2*poz+1];
}
void query(int poz,int st,int dr,int sI,int dI)
{
    if(sI<=st&&dr<=dI)
        {
            rasp+=ai[poz];
            return;
        }

    int mij=(st+dr)/2;
    if(mij>=sI)
        query(2*poz,st,mij,sI,dI);
    if(mij<dI)
        query(2*poz+1,mij+1,dr,sI,dI);
}
int n;
void citire()
{
    scanf("%d",&n);
    for(int i=1; i<=2*n; i+=2)
    {
        scanf("%d%d%d%d",&vCit[i].x,&vCit[i].y,&vCit[i+1].x,&vCit[i+1].y);
        if(vCit[i].y==vCit[i+1].y)
        {
            vCit[i].orizontal=true;
            vCit[i+1].orizontal=true;
        }
        else
        {
            vCit[i].orizontal=false;
            vCit[i+1].orizontal=false;

        }
        maxY=max(maxY,max(vCit[i].y,vCit[i+1].y));
        minY=min(minY,min(vCit[i].y,vCit[i+1].y));
    }
}
int main()
{
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
    citire();
    int raspuns=0;
    sort(vCit+1,vCit+2*n+1,cmp);
    for(int i=1; i<=2*n; i++)
    {
        if(vCit[i].orizontal)
            actualizare(1,minY,maxY,vCit[i].y);
        else
        {
            rasp=0;
            query(1,minY,maxY,vCit[i].y,vCit[i+1].y);
            ++i;
            raspuns+=rasp;
        }
    }
    printf("%d",raspuns);
    return 0;
}