题解：P13396 [GCJ 2010 #1C] Rope Intranet

_czl_ · 2025-07-22 19:53:33 · 题解

题解：P13396 [GCJ 2010 #1C] Rope Intranet

题目链接

思路

考虑暴力枚举所有可能的电线对，判断它们在左侧建筑的高度顺序与右侧建筑的高度顺序相反，统计满足条件的对数即可。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    for(int k=1;k<=t;k++)
    {
        s=0;
        cin>>n;
        vector<pair<int,int>> wires(n);
        for(auto& w:wires) cin>>w.first>>w.second;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                if((wires[i].first<wires[j].first)^(wires[i].second<wires[j].second))
                    s++;
        cout<<"Case #"<<k<<": "<<s<<'\n';
    }
    return 0;
}