求助
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/27 16:17
  • 上次更新2024/7/27 17:08:57
查看原帖
求助
973480
封禁用户楼主2024/7/27 16:17

问题描述 FJ有 NN 头奶牛,奶牛们在牧场中活动。牧场是一个二维的平面,奶牛们只从 Y=0Y=0 的水平线上,以直线走到 Y=1Y=1 的点上。一开始,奶牛们都在 (Ai,0)(A _i,0) 上,再以直线的方式走到 (Bi,1)(B_i,1) 上,由于奶牛们的个性不一样,走的过程中,有些奶牛走的线路可能会相交,这样会不安全。求其中安全路线的条数。

输入格式 第 1 行,一个整数 NN;

第 22 到 N+1N+1 行,每行两个整数 AiA_i 和 BiB _i,描述如题意。

所有的 AiA_i 保证不相等;所有的 BiB_i 保证不相等

输出格式
输出共一行一个整数 RetRet,即安全路线的条数。
输入数据 1\

4 
-3 4
7 8
10 16
3 9

输出数据 1

2

样例解释
第1条和第3条是安全路线。

数据规模
对于 4040% 的数据:1≤N≤50001≤N≤5000;

对于 100100% 的数据: 1≤N≤100000;0≤∣Ai∣,∣Bi∣≤1,000,000;1≤N≤100000;0≤∣Ai∣,∣B i∣≤1,000,000;

#include <iostream>
#include <algorithm>
using namespace std;
struct Cow {
    int a, b;
}cow[100001];
bool f(Cow c1,Cow c2){
    return ((c1.a <= c2.a && c1.b < c2.b) || (c1.a > c2.a && c1.b > c2.b));
}
int main() {
    int n,cnt=1;
    cin >> n;
    for(int i=n;i>=1;i--){
        for(int j=1;j<i;j++){
            if(f(cow[i],cow[j])) cnt++;
        }
    }
    cout << cnt;
    return 0;
}
2024/7/27 16:17
加载中...