USACO23FEB-Silver B
题目来源(From)
洛谷: USACO23FEB-Silver Cow Libi(B)
SPOJ:USACO23FEB-Silver Cow Libi(B) - 题面
题解: USACO23FEB-Silver Cow Libi(B) - 题解
题目(Problem)
题目描述(中文)
输入格式
输出格式
样例
输入数据 1
2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170
输出数据 1
2
样例1说明
数据规模与约定
- 测试点
: ;此外,对于在现场和不在场证明, 且 。 - 测试点
:没有其它约定。
题解(Solution)
一些需要注意的地方:
- 题目中的距离指的是欧几里得距离,而非曼哈顿距离。
- 本题对精度要求很高。
- 如果某个不在场证明时间比所有吃草事件都早或都晩,那么需要特判。
代码(Code)
我的代码
#include<bits/stdc++.h>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define double long double
#define int long long
#define Fi first
#define Se second
inline double input(){double x;return cin>>x,x;}
const int N = 101234;
int g,n;
struct T{
double x,y,t;
bool operator<(const T y){return t<y.t;}
}cow[N],pla[N];
bitset<N> ava;
inline double dis(double x1,double y1,double x2,double y2){return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
inline bool check(T a,T b,double lmt){return lmt<dis(a.x,a.y,b.x,b.y);}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string str("b");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
cin>>g>>n;
For(i,1,g) pla[i]={input(),input(),input()};
sort(pla+1,pla+g+1);
For(i,1,n){
cow[i]={input(),input(),input()};
int pos1=lower_bound(pla+1,pla+g+1,cow[i])-pla;
int pos2=pos1-1;
if(1<=pos1 && pos1<=g) ava[i]=ava[i]|check(cow[i],pla[pos1],abs(pla[pos1].t-cow[i].t));
if(1<=pos2 && pos2<=g) ava[i]=ava[i]|check(cow[i],pla[pos2],abs(pla[pos2].t-cow[i].t));
}cout<<ava.count()<<'\n';
return 0;
}
后续(Ending)
第一次一道黄题没有一个人