HDU6681 Rikka with Cake

93 阅读 0 评论 62 点赞

我是靠谱客的博主魔幻雪碧，这篇文章主要介绍HDU6681 Rikka with Cake，现在分享给大家，希望可以做个参考。

测试地址

题意简述

直接看样例其实就明白了，看图说话，就是给出一个左下角坐标为(0,0)，右上角为(n,m)的矩形；然后有k条线段，这些线段不重叠，都是从矩形内某一点出发到矩形某一边为止，这些线段共四种，都与坐标轴平行。
在这里插入图片描述
请问这些线段将矩形分为了几个不连通的面？（图一是3个，图二是5个）

解题思路

首先考虑到任意两条直线的x，y坐标都是不同的，所以不会出现重叠现象。观察得，肯定是相交的线段才能分割出新的面（一条横的线与几条竖线相交就会增加几个面）。
所以我们只需考虑，假设先将所有与y轴平行的线加入，然后对于每一条与x轴平行的线，有几条与其相交，最终答案就是这些交点个数再+1。

现在的问题就是对于每个与x轴平行的线，有多少与y轴平行的线与其相交。如果挨个计算并累加，计算完所有线段需要O(N^2)时间。其实我们会发现，找与(x , y)至左边界（L）的横线相交的线段，只需要找出 x’ <= x && y’ <= y的向上方(U) 的线段以及 x’ <= x && y’ >= y的向下 (D) 的线段的数量即可。这是二维偏序问题，是4个二维偏序问题。而二维偏序问题可以在 $O(Nlog_2^N)$ 时间内用CDQ分治解决，写起来也不是很麻烦（还好不是三维）。

代码示例

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5+10;
struct Node{
    int x,y,t;
    Node(){}
    Node(int x,int y):x(x),y(y){t = 0;}
    bool operator < (const Node& B)const{
        return x < B.x;
    }
};
Node U[N],D[N],R[N],L[N],tmp[N];
Node TU[N];
int cu,cd,cr,cl,cnt;
int n,m,t,k;
void cdq1(int l,int r){
    if(l >= r-1) return;
    int mid = l+r>>1;
    cdq1(l,mid); cdq1(mid,r);
    int p = l,q = mid,tk = 0,tt = 0;
    while(p < mid && q < r){
        if(TU[p].y <= TU[q].y){
            if(!TU[p].t) tt++;
            tmp[tk++] = TU[p++];

} else{
            if(TU[q].t) cnt += tt;
            tmp[tk++] = TU[q++];
        }
    }
    while(p < mid) tmp[tk++] = TU[p++];
    while(q < r){
        if(TU[q].t) cnt += tt;
        tmp[tk++] = TU[q++];
    }
    for(int i = 0;i < tk;i++) TU[i+l] = tmp[i];
}
bool cmp2(Node a,Node b){
    return a.x > b.x;
}
void solve(){
/*
    对于L[i],有多少U中x < L[i].x && y < L[i].y,
            有多少D中x < L[i].x && y > L[i].y;
    对于R[i]有多少U中x > R[i].x && y < R[i].y,
            有多少D中x > R[i].x && y > R[i].y;
*/
    cnt = 0;
    for(int i = 0;i < cu;i++) TU[i] = U[i];
    for(int i = 0;i < cl;i++) TU[i+cu] = L[i],TU[i+cu].t = 1;
    stable_sort(TU,TU+cu+cl);
    cdq1(0,cl+cu);

for(int i = 0;i < cd;i++) TU[i] = D[i];
    for(int i = 0;i < cl;i++) TU[i+cd] = L[i],TU[i+cd].t = 1;
    for(int i = 0;i < cl+cd;i++) TU[i].y *= -1;
    stable_sort(TU,TU+cd+cl);
    cdq1(0,cl+cd);

for(int i = 0;i < cu;i++) TU[i] = U[i];
    for(int i = 0;i < cr;i++) TU[i+cu] = R[i],TU[i+cu].t = 1;
    stable_sort(TU,TU+cr+cu,cmp2);
    //for(int i = 0;i < cr+cu;i++) printf("%d %dn",TU[i].x,TU[i].y);
    cdq1(0,cr+cu);

for(int i = 0;i < cd;i++) TU[i] = D[i];
    for(int i = 0;i < cr;i++) TU[i+cd] = R[i],TU[i+cd].t = 1;
    for(int i = 0;i < cd+cr;i++) TU[i].y *= -1;
    stable_sort(TU,TU+cr+cd,cmp2);
    cdq1(0,cr+cd);
    printf("%dn",cnt+1);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        cu = cd = cr = cl = 0;
        for(int i = 1;i <= k;i++){
            int x,y;char dir[5];
            scanf("%d%d%s",&x,&y,dir);
            if(dir[0] == 'U') U[cu++] = Node(x,y);
            else if(dir[0] == 'D') D[cd++] = Node(x,y);
            else if(dir[0] == 'L') L[cl++] = Node(x,y);
            else R[cr++] = Node(x,y);
        }
        solve();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5+10;
struct Node{
    int x,y,t;
    Node(){}
    Node(int x,int y):x(x),y(y){t = 0;}
    bool operator < (const Node& B)const{
        return x < B.x;
    }
};
Node U[N],D[N],R[N],L[N],tmp[N];
Node TU[N];
int cu,cd,cr,cl,cnt;
int n,m,t,k;
void cdq1(int l,int r){
    if(l >= r-1) return;
    int mid = l+r>>1;
    cdq1(l,mid); cdq1(mid,r);
    int p = l,q = mid,tk = 0,tt = 0;
    while(p < mid && q < r){
        if(TU[p].y <= TU[q].y){
            if(!TU[p].t) tt++;
            tmp[tk++] = TU[p++];

        } else{
            if(TU[q].t) cnt += tt;
            tmp[tk++] = TU[q++];
        }
    }
    while(p < mid) tmp[tk++] = TU[p++];
    while(q < r){
        if(TU[q].t) cnt += tt;
        tmp[tk++] = TU[q++];
    }
    for(int i = 0;i < tk;i++) TU[i+l] = tmp[i];
}
bool cmp2(Node a,Node b){
    return a.x > b.x;
}
void solve(){
/*
    对于L[i],有多少U中x < L[i].x && y < L[i].y,
            有多少D中x < L[i].x && y > L[i].y;
    对于R[i]有多少U中x > R[i].x && y < R[i].y,
            有多少D中x > R[i].x && y > R[i].y;
*/
    cnt = 0;
    for(int i = 0;i < cu;i++) TU[i] = U[i];
    for(int i = 0;i < cl;i++) TU[i+cu] = L[i],TU[i+cu].t = 1;
    stable_sort(TU,TU+cu+cl);
    cdq1(0,cl+cu);

    for(int i = 0;i < cd;i++) TU[i] = D[i];
    for(int i = 0;i < cl;i++) TU[i+cd] = L[i],TU[i+cd].t = 1;
    for(int i = 0;i < cl+cd;i++) TU[i].y *= -1;
    stable_sort(TU,TU+cd+cl);
    cdq1(0,cl+cd);

    for(int i = 0;i < cu;i++) TU[i] = U[i];
    for(int i = 0;i < cr;i++) TU[i+cu] = R[i],TU[i+cu].t = 1;
    stable_sort(TU,TU+cr+cu,cmp2);
    //for(int i = 0;i < cr+cu;i++) printf("%d %dn",TU[i].x,TU[i].y);
    cdq1(0,cr+cu);

    for(int i = 0;i < cd;i++) TU[i] = D[i];
    for(int i = 0;i < cr;i++) TU[i+cd] = R[i],TU[i+cd].t = 1;
    for(int i = 0;i < cd+cr;i++) TU[i].y *= -1;
    stable_sort(TU,TU+cr+cd,cmp2);
    cdq1(0,cr+cd);
    printf("%dn",cnt+1);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        cu = cd = cr = cl = 0;
        for(int i = 1;i <= k;i++){
            int x,y;char dir[5];
            scanf("%d%d%s",&x,&y,dir);
            if(dir[0] == 'U') U[cu++] = Node(x,y);
            else if(dir[0] == 'D') D[cd++] = Node(x,y);
            else if(dir[0] == 'L') L[cl++] = Node(x,y);
            else R[cr++] = Node(x,y);
        }
        solve();
    }
    return 0;
}