HDU 5862 Counting Intersections (이산 화 + 트 리 배열)

제목 의 대의
n 개의 수평 또는 수직 선분 을 정 하고 모든 선분 의 교점 개 수 를 통계 합 니 다.（n<=100000）
문제 풀이 분석
우선 선분 을 이산 화하 다.
그 다음 에 모든 선분 을 가로 좌표 의 순서에 따라 먼저 삽입 한 다음 에 찾 은 다음 에 삭제 하 는 순서에 따라 조작 합 니 다.
횡선 이 왼쪽 단점 이 라면 세로 좌 표를 1 로 하고 오른쪽 단점 은 1 로 줄 이 며 세로 선 에 대해 서 는 직접 화 해 를 구하 면 된다.
정렬 할 때 세로 선 을 우선 처리 해 야 합 니 다. 세로 선 이 마침 가로 선 왼쪽 점 과 교차 하 는 상황 이 있 기 때 문 입 니 다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define L(i) i<<1
#define R(i) i<<1|1
#define INF  0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-4
#define maxn 100010
#define MOD 1000000007

int n;
struct node
{
    int x,y1,y2;
    int flag;
    bool operator  a.flag);
    }
}cnt[maxn<<1];

map mp;
int a[maxn<<1];
long long c[maxn<<1];
void update(int x,long long add)
{
    while(x < (maxn<<1))
    {
        c[x] += add;
        x += x & (-x);
    }
}
long long get_sum(int x)
{
    long long sum = 0;
    while(x)
    {
        sum += c[x];
        x -= x & (-x);
    }
    return sum;
}
int main()
{
    int t,C = 1;
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        int k = 0;
        for(int i = 0; i < n; i++)
        {
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1 == x2)
            {
                if(y1 > y2)
                    swap(y1,y2);
                cnt[k].x = x1;
                cnt[k].y1 = y1;
                cnt[k].y2 = y2;
                cnt[k++].flag = 0;
            }
            else
            {
                if(x1 > x2)
                    swap(x1,x2);
                cnt[k].x = x1;
                cnt[k].y1 = y1;
                cnt[k].y2 = y2;
                cnt[k++].flag = 1;
                cnt[k].x = x2+1;
                cnt[k].y1 = y1;
                cnt[k].y2 = y2;
                cnt[k++].flag = 2;
            }
            a[2*i] = y1;
            a[2*i+1] = y2;
        }
        sort(a,a+2*n);
        mp.clear();
        int len = unique(a,a+2*n) - a;
        for(int i = 1; i <= len; i++)
            mp[a[i-1]] = i;
        sort(cnt,cnt+k);
        long long ans = 0;
        for(int i = 0; i < k; i++)
        {
            if(!cnt[i].flag)
                ans += get_sum(mp[cnt[i].y2]) - get_sum(mp[cnt[i].y1]-1);
            else if(cnt[i].flag == 1)
                update(mp[cnt[i].y1],1);
            else
                update(mp[cnt[i].y1],-1);
        }
        printf("%lld
",ans);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[Educational Codeforces Round 10D] [트 리 배열] Nested Segments 각 라인 내부 에 몇 개의 라인 이 있 습 니까?

D. Nested Segments time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standar...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 5862 Counting Intersections (이산 화 + 트 리 배열)

좋은 웹페이지 즐겨찾기