QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187462 | #3854. Radar | Flying2018# | Compile Error | / | / | C++14 | 3.4kb | 2023-09-24 17:33:46 | 2023-09-24 17:33:46 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define db double
using namespace std;
const db eps=1e-8;
const db inf=1e20;
int sgn (db x){
if(fabs(x)<eps)return 0;
if(x<0)return -1;
return 1;
}
int comp (double x,double y){
return sgn(x-y);
}
bool Less(double x,double y){
return comp(x,y)==-1;
}
const int MAXN=2e5+7;
struct point{
double x,y;
point(){};
point(db _x,db _y):x(_x),y(_y){};
double operator^(const point &b)const {
return x * b.y - y *b.x;
}
double operator*(const point &b){
return x * b.x + y * b.y;
}
point operator+(const point &b)const {
return point(x+b.x,y+b.y);
}
point operator-(const point &b)const {
return point(x-b.x,y-b.y);
}
point operator*(const double &k)const{
return point(x*k,y*k);
}
point operator/(const double &k)const{
return point(x/k,y/k);
}
double len2()
{
return x*x+y*y;
}
double len(){
return hypot(x,y);
}
double distance(point p){
return hypot(x-p.x,y-p.y);
}
}a[MAXN];
struct Line {
point p;
point v;
double rad;
Line(){};
Line(point _p,point _v):p(_p),v(_v){
rad = atan2(v.y,v.x);
};
bool operator<(const Line &x){
return Less(rad,x.rad);
}
point lineprog(point a){
return p+(((v-p)*((v-p)*(a-p)))/(v-p).len2());
}
}b[MAXN];
bool cmprad(Line A,Line B){
return Less(A.rad,B.rad);
}
int R,F,N;
int rl[MAXN];
db nans;
inline void calc(point a,db d,point b){
// printf("%lf %lf -> b\n",a.x/a.len()*d,a.y/a.len()*d);
point a0 = point(a.x/a.len()*d,a.y/a.len()*d);
nans=min(nans,a0.distance(b));
}
inline void check(Line a,point b){
// printf("%lf %lf ?!\n",a.v.x,a.v.y);
point tmp = a.lineprog(b);
// printf("%lf %lf %lf %lf\n",b.x,b.y,tmp.x,tmp.y);
int t= lower_bound(rl+1,rl+R+1,tmp.len()) - rl;
// printf("%lf %d\n",b.len(),rl[t]);
calc(a.v,rl[1],b);
calc(a.v,rl[R],b);
if(t!=R+1){
if(t!=R)calc(a.v,rl[t+1],b);
calc(a.v,rl[t],b);
if(t!=1)calc(a.v,rl[t-1],b);
}
}
inline void solve(){
for(int i=1;i<=N;++i){
int t = lower_bound(b+1,b+F+1,Line(point(0,0),a[i]),Less) - b;
nans=1e18;
// printf("now %d %d\n",i,t);
if(t==F+1 || t==1){
check(b[1],a[i]);
check(b[F],a[i]);
}else {
check(b[t],a[i]);
check(b[t-1],a[i]);
if(t!=F)check(b[t+1],a[i]);
}
printf("%.12lf\n",nans);
}
return ;
}
int main(){
scanf("%d%d%d",&R,&F,&N);
for(int i=1;i<=R;++i){
scanf("%d",&rl[i]);
}
sort(rl+1,rl+R+1);
for(int i=1;i<=F;++i){
scanf("%lf%lf",&a[i].x,&a[i].y);
b[i]=Line(point(0.0,0.0),point(a[i].x,a[i].y));
}
sort(b+1,b+F+1,cmprad);
// printf("%lf %lf %lf %lf\n",atan2(3,0),atan2(-2,0),atan2(0,3),atan2(0,-3));
// for(int i=1;i<=F;++i){
// printf("%lf %lf\n",b[i].v.x,b[i].v.y);
// }
for(int i=1;i<=N;++i){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
solve();
return 0;
}
/*
3 1 1
1 2 3
3 3
1 -2
3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1
*/
Details
In file included from /usr/include/c++/11/bits/stl_algobase.h:71, from /usr/include/c++/11/bits/char_traits.h:39, from /usr/include/c++/11/ios:40, from /usr/include/c++/11/ostream:38, from /usr/include/c++/11/iostream:39, from answer.code:1: /usr/include/c++/11/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = Line*; _Value = const Line; _Compare = bool (*)(double, double)]’: /usr/include/c++/11/bits/stl_algobase.h:1464:14: required from ‘_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = Line*; _Tp = Line; _Compare = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(double, double)>]’ /usr/include/c++/11/bits/stl_algo.h:2021:32: required from ‘_FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = Line*; _Tp = Line; _Compare = bool (*)(double, double)]’ answer.code:107:28: required from here /usr/include/c++/11/bits/predefined_ops.h:196:30: error: cannot convert ‘Line’ to ‘double’ in argument passing 196 | { return bool(_M_comp(*__it, __val)); } | ~~~~~~~^~~~~~~~~~~~~~ answer.code: In function ‘int main()’: answer.code:124:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 124 | scanf("%d%d%d",&R,&F,&N); | ~~~~~^~~~~~~~~~~~~~~~~~~ answer.code:126:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 126 | scanf("%d",&rl[i]); | ~~~~~^~~~~~~~~~~~~ answer.code:130:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 130 | scanf("%lf%lf",&a[i].x,&a[i].y); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~ answer.code:139:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 139 | scanf("%lf%lf",&a[i].x,&a[i].y); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~