Rikka with Cake

84 阅读 0 评论 56 点赞

我是靠谱客的博主稳重月饼，最近开发中收集的这篇文章主要介绍Rikka with Cake，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Rikka’s birthday is on June 12th. The story of this problem happens on that day.
Today is Rikka’s birthday. Yuta prepares a big cake for her: the shape of this cake is a rectangular of n centimeters times m centimeters. With the guidance of a grimoire, Rikka is going to cut the cake.
For simplicity, Rikka firstly builds a Cartesian coordinate system on the cake: the coordinate of the left bottom corner is (0,0) while that of the right top corner is (n,m). There are K instructions on the grimoire: The ith cut is a ray starting from (xi,yi) while the direction is Di. There are four possible directions: L, passes (xi−1,yi); R, passes (xi+1,yi); U, passes (xi,yi+1); D, passes (xi,yi−1).
Take advantage of the infinite power of Tyrant’s Eye, Rikka finishes all the instructions quickly. Now she wants to count the number of pieces of the cake. However, since a huge number of cuts have been done, the number of pieces can be very large. Therefore, Rikka wants you to finish this task.

Input
The first line of the input contains a single integer T(1≤T≤100), the number of the test cases.
For each test case, the first line contains three positive integers n,m,K(1≤n,m≤109,1≤K≤105), which represents the shape of the cake and the number of instructions on the grimoire.
Then K lines follow, the ith line contains two integers xi,yi(1≤xi<n,1≤yi<m) and a char Di∈{‘L’,‘R’,‘U’,‘D’}, which describes the ith cut.
The input guarantees that there are no more than 5 test cases with K>1000, and no two cuts share the same x coordinate or y coordinate, i.e., ∀1≤i<j≤K, xi≠xj and yi≠yj.

Output
For each test case, output a single line with a single integer, the number of pieces of the cake.

Hint
The left image and the right image show the results of the first and the second test case in the sample input respectively. Clearly, the answer to the first test case is 3 while the second one is 5.
在这里插入图片描述
Sample Input
2
4 4 3
1 1 U
2 2 L
3 3 L
5 5 4
1 2 R
3 1 U
4 3 L
2 4 D

Sample Output
3
5

用欧拉（欧拉欧拉欧拉）公式来算蛋糕的块数。
首先考虑点数，蛋糕的四个角以及射线的端点贡献了个顶点（太丑了我们用表示射线数），射线和四条边的交点共有个，射线之间的交点有个，因此点数是。接着考虑边数，对于每一条射线，假设别的射线和他的交点有个，那么这条射线被切成了段，因此所有射线的边数对应的是（因为每一个交点被用了两次）。同时因为四条边一共和射线交了次，所以四条边界上共有条边，所以。因此总的区域数为，因为要去掉外面的无穷区域，所以答案就是。于是问题就变成了求交点个数。这是一个经典的问题，分四个方向讨论一下离散化用树状数组求就行。时间复杂度 O(nlogn)

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
typedef long long ll;
struct Point{
    int x,y;
    char dir;
}p1[maxn],p2[maxn];
int X[maxn],Y[maxn],c[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int d){
    while(x<=maxn){
        c[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x){
    int res=0;
    while(x>0){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
bool cmp(Point a,Point b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        int n,m,k; scanf("%d%d%d",&n,&m,&k);
        int cnt1=0,cnt2=0,tot=0;
        for(int i=1;i<=k;i++){
            getchar();
            int x,y; char c;
            scanf("%d %d %c",&x,&y,&c);
            if(c=='U'||c=='D'){
                p1[++cnt1].x=x; p1[cnt1].y=y; p1[cnt1].dir=c;
            }
            else{
                p2[++cnt2].x=x; p2[cnt2].y=y; p2[cnt2].dir=c;
            }
            X[++tot]=x; Y[tot]=y;
        }
        sort(X+1,X+tot+1);
        sort(Y+1,Y+tot+1);
        int num1=unique(X+1,X+tot+1)-(X+1);
        int num2=unique(Y+1,Y+tot+1)-(Y+1);
        for(int i=1;i<=cnt1;i++){
            p1[i].x=lower_bound(X+1,X+num1+1,p1[i].x)-X;
            p1[i].y=lower_bound(Y+1,Y+num2+1,p1[i].y)-Y;
        } 
        for(int i=1;i<=cnt2;i++){
            p2[i].x=lower_bound(X+1,X+num1+1,p2[i].x)-X;
            p2[i].y=lower_bound(Y+1,Y+num2+1,p2[i].y)-Y;
        }
        n=lower_bound(X+1,X+num1+1,n)-X;
        m=lower_bound(Y+1,Y+num2+1,m)-Y;
        sort(p1+1,p1+cnt1+1,cmp);
        sort(p2+1,p2+cnt2+1,cmp);
        memset(c,0,sizeof(c));
        for(int i=1;i<=cnt2;i++){
            if(p2[i].dir=='L') add(p2[i].y,1);
        }
        ll ans=1,j=1;
        for(int i=1;i<=cnt1;i++){
            while(j<=cnt2 && p2[j].x<p1[i].x){
                if(p2[j].dir=='L') add(p2[j].y,-1); 
                j++;
            }
            if(p1[i].dir=='U'){
                ans+=sum(m)-sum(p1[i].y-1);
            }
            else ans+=sum(p1[i].y);
        }
        memset(c,0,sizeof(c));
        for(int i=1;i<=cnt2;i++){
            if(p2[i].dir=='R') add(p2[i].y,1);
        }
        j=cnt2;
        for(int i=cnt1;i>=1;i--){
            while(j>=1 && p2[j].x>p1[i].x){
                if(p2[j].dir=='R') add(p2[j].y,-1); 
                j--;
            }
            if(p1[i].dir=='U'){
                ans+=sum(m)-sum(p1[i].y-1);
            }
            else ans+=sum(p1[i].y);
        }
        printf("%lldn",ans);
    }
    return 0;
}