题目:

“我们的婚礼仪式是庄严、清醒的反思时刻;还有遗憾、分歧、争论和相互指责。一旦你知道事情不会变得更糟，你就可以放松并享受婚姻。J.Michael Straczynski，“流星的解构”。半人马座的公主银河系最可辨认的年度单身女郎。她有充满希望的新郎在皇宫的前面，花 5 分钟尝试并给她留下深刻印象。5分钟后，绅士被宫殿卫兵抬出皇家房间，公主做出决定。她通过将他作为两个属性中每个属性的核心来评价拉登的血统年龄和魅力。在 Centauri Prime 上，低分比高分好。假设她观察了两个绅士-A和B。她给A分配了LA和CA的分数（分别是血统和魅力）。B接受分数LB和CB.然后A is 主要由B if要么•LB<LA and CB≤CA，要么•LB≤L A and CB<CA主导。换句话说，B的分数比A的分数好，而其他分数并不差。她认为绅士是有效的（或帕累托最优的），如果她还没有遇到任何其他统治他的绅士。她保持高效的美容和更新，每次 5 分钟的演示。给定单身汉的队列和由公主分配给他们的分数，确定每次表演后高效新郎名单中的条目数量。

输入

输入的第一行给出了案例数，N（0<N<40）。N个测试用例。每个人开始时包含 a line contain in gn（0≤n≤15000）—队列的大小。接下来的 n 行将每个包含两个分数（integers in the range[0,1e9]）。最初，列表是空的。

输出

每个测试用例，输出包含“案例#x：”的行，线图标包含高效新郎列表的大小。在测试用例之间打印一个空行。

下面将L当作x,C当做y,从而更容易与平面几何联系起来

大概题意:

求出每次输入数据后,不存在other.x <= this->x && other.y < this->y 或者other.x < this->x && other.y <= this->y 的this点的个数

大概思路:

以x和y为横纵坐标,画到平面图中就是求有多少个点,它和两坐标轴围成的区域中,没有其他点(但可以有与这个点重合的点),我们想到在画上当前所有点的平面坐标系中,把最靠左下那一圈凹进去的部分连起来(选出来),就是题目要求的点,(相当于躲着其它点)

然后每加入一个点,按x坐标排,如果x在他左边,那么高度就要>它,不然就把那个点包进去了,如果与它重合(x,y均相等)那也行.然后插入这个点,会影响它右边的点,会让右边所有>=的点的点,把它包进去,这些点就不是优势点了

注意这个题重载了<比较运算符(为什么要从小到大排序?:因为要用到二分查找找>=和>他的点,前提条件是他得从小到大排序,不然又要用greater<>,比较麻烦).

关键:搞清楚重载了<运算符后,调用lower_bound与upper_bound找到的位置符合什么条件,才知道下一步要干嘛

AC代码:

#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int x,y;
    bool operator < (const node& other) const {
        return x < other.x || (x == other.x && y < other.y);//x作为第一关键字,y作为第二关键字
    }
};
int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int n,len;cin>>n;
    for(int i=1;i<=n;i++) {
        cout<<"Case #"<<i<<':'<<'\n';
        multiset<node> ms;
        cin>>len;
        int tx,ty;
        for(int j=1;j<=len;j++) {
            cin>>tx>>ty;
            node tmp={tx,ty};
            auto it=ms.lower_bound(tmp);//第一个>=它,即x> || x== && y>=
          //由于y为第二关键字,所以--it是第一个 x< || x== && y< 它的位置,所以--it->y>当前的y
            if (it==ms.begin() || (--it)->y > tmp.y) {//若it==ms.begin()最左边那个位置就x>或x==它了,它当前与坐标轴围成的区域一定不会包含任何点,>排除了x< 但y<=当前插入这个点的情况,也排除了x== && y<这种情况.
                ms.insert(tmp);//加入到具有优势的点的集合中(可重复)
                it=ms.upper_bound(tmp);//找第一个x== &&y> || x> 它的,这是别人相对它的位置,看别人对他的影响,就有看他相对于别人的位置,即x== && y<= || x<别人
                while (it!=ms.end()/*end是最后一个位置+1的迭代器*/ && it->y >= tmp.y) {
                    ms.erase(it++);//除了 别人x>它 && y< 它这种情况,其他情况下假如这个点都会使别人不具优势
                }
            }
            cout<<ms.size()<<'\n';//时刻输出具有优势的点的个数
        }
        cout<<'\n';//记得换行
    }
    return 0;
}