问题描述 FJ有 N 头奶牛,奶牛们在牧场中活动。牧场是一个二维的平面,奶牛们只从 Y=0 的水平线上,以直线走到 Y=1 的点上。一开始,奶牛们都在 (Ai,0) 上,再以直线的方式走到 (Bi,1) 上,由于奶牛们的个性不一样,走的过程中,有些奶牛走的线路可能会相交,这样会不安全。求其中安全路线的条数。
输入格式 第 1 行,一个整数 N;
第 2 到 N+1 行,每行两个整数 Ai 和 Bi,描述如题意。
所有的 Ai 保证不相等;所有的 Bi 保证不相等
输出格式
输出共一行一个整数 Ret,即安全路线的条数。
输入数据 1\
4
-3 4
7 8
10 16
3 9
输出数据 1
2
样例解释
第1条和第3条是安全路线。
数据规模
对于 40% 的数据:1≤N≤5000;
对于 100% 的数据: 1≤N≤100000;0≤∣Ai∣,∣Bi∣≤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;
}