QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#953403 | #9668. Isoball: 2D Version | pheonix_2002# | AC ✓ | 12ms | 3840kb | C++20 | 7.7kb | 2025-03-27 19:27:44 | 2025-03-27 19:27:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using T = long double;
// const int eps=0;
constexpr T eps=1e-9;
constexpr T INF=numeric_limits<T>::max();
constexpr T PI=3.1415926535897932384l;
struct Point
{
T x,y;
bool operator==(const Point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const Point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const Point &a) const {return !(*this<a || *this==a);}
Point operator+(const Point &a) const {return {x+a.x,y+a.y};}
Point operator-(const Point &a) const {return {x-a.x,y-a.y};}
Point operator-() const {return {-x,-y};}
Point operator*(const T k) const {return {k*x,k*y};}
Point operator/(const T k) const {return {x/k,y/k};}
T operator*(const Point &a) const {return x*a.x+y*a.y;} // 鐐圭Н
T operator^(const Point &a) const {return x*a.y-y*a.x;} // 鍙夌Н锛屾敞鎰忎紭鍏堢骇
int toleft(const Point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // to-left 娴嬭瘯
T len2() const {return (*this)*(*this);} // 鍚戦噺闀垮害鐨勫钩鏂?
T dis2(const Point &a) const {return (a-(*this)).len2();} // 涓ょ偣璺濈鐨勫钩鏂?
int quad() const // 璞¢檺鍒ゆ柇 0:鍘熺偣 1:x杞存 2:绗竴璞¢檺 3:y杞存 4:绗簩璞¢檺 5:x杞磋礋 6:绗笁璞¢檺 7:y杞磋礋 8:绗洓璞¢檺
{
if (abs(x)<=eps && abs(y)<=eps) return 0;
if (abs(y)<=eps) return x>eps ? 1 : 5;
if (abs(x)<=eps) return y>eps ? 3 : 7;
return y>eps ? (x>eps ? 2 : 4) : (x>eps ? 8 : 6);
}
// 蹇呴』鐢ㄦ诞鐐规暟
T len() const {return sqrtl(len2());} // 鍚戦噺闀垮害
T dis(const Point &a) const {return sqrtl(dis2(a));} // 涓ょ偣璺濈
T ang(const Point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));} // 鍚戦噺澶硅
Point rot(const T rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 閫嗘椂閽堟棆杞紙缁欏畾瑙掑害锛?
Point rot(const T cosr,const T sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 閫嗘椂閽堟棆杞紙缁欏畾瑙掑害鐨勬寮︿笌浣欏鸡锛?
};
// bool argcmp(const Point &a,const Point &b)
// {
// return (a^b)>eps;
// }
// 鍗婂钩闈㈡瀬瑙掓帓搴?
bool argcmp(const Point &a,const Point &b)
{
auto quad=[](const Point &a)
{
if (a.y<-eps) return 1;
if (a.y>eps) return 4;
if (a.x<-eps) return 5;
if (a.x>eps) return 3;
return 2;
};
int qa=quad(a),qb=quad(b);
if (qa!=qb) return qa<qb;
auto t=a^b;
if (abs(t)<=eps) return a*a<b*b-eps;
return t>eps;
}
struct Argcmp
{
bool operator()(const Point &a,const Point &b) const
{
const int qa=a.quad(),qb=b.quad();
if (qa!=qb) return qa<qb;
const auto t=a^b;
// if (abs(t)<=eps) return a*a<b*b-eps; // 涓嶅悓闀垮害鐨勫悜閲忛渶瑕佸垎寮€
return t>eps;
}
};
// 鍏ㄥ钩闈㈡瀬瑙掓帓搴?
struct Line
{
Point p,v; // p 涓虹洿绾夸笂涓€鐐癸紝v 涓烘柟鍚戝悜閲?
bool operator==(const Line &a) const {return v.toleft(a.v)==0 && v.toleft(p-a.p)==0;}
int toleft(const Point &a) const {return v.toleft(a-p);} // to-left 娴嬭瘯
bool operator<(const Line &a) const // 鍗婂钩闈氦绠楁硶瀹氫箟鐨勬帓搴?
{
if (abs(v^a.v)<=eps && v*a.v>=-eps) return toleft(a.p)==-1;
return Argcmp()(v,a.v);
}
// 蹇呴』鐢ㄦ诞鐐规暟
Point inter(const Line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));} // 鐩寸嚎浜ょ偣
T dis(const Point &a) const {return abs(v^(a-p))/v.len();} // 鐐瑰埌鐩寸嚎璺濈
Point proj(const Point &a) const {return p+v*((v*(a-p))/(v*v));} // 鐐瑰湪鐩寸嚎涓婄殑鎶曞奖
bool is_point_on_ray(const Point &p, const Line &ray) {
if ((p - ray.p).len() < eps) return true; // 涓庤捣鐐归噸鍚?
Point v = p - ray.p;
// 鏂瑰悜鐩稿悓涓旂偣绉?>= 0
return abs(v ^ (ray.v)) < eps && v * (ray.v) >= -eps;
}
pair<bool, Point> ray_segment_intersection(const Line &ray, const Point &p1, const Point &p2) {
Point seg_dir = p2 - p1;
T denom = ray.v ^ (seg_dir);
if (abs(denom) < eps) { // 骞宠鎴栭噸鍚?
if (is_point_on_ray(p1, ray)) return {true, p1};
if (is_point_on_ray(p2, ray)) return {true, p2};
return {false, Point()};
}
T t = (p1 - ray.p) ^ (seg_dir) / denom;
T u = (p1 - ray.p) ^ (ray.v) / denom;
if (t < -eps || u < -eps || u > 1 + eps)
return {false, Point()}; // 浜ょ偣鍦ㄥ皠绾垮弽鏂瑰悜鎴栫嚎娈靛
Point inter = ray.p + ray.v * t;
return {true, inter};
}
};
//绾挎
struct Segment
{
Point a,b;
bool operator<(const Segment &s) const {return make_pair(a,b)<make_pair(s.a,s.b);}
// 鍒ゅ畾鎬у嚱鏁板缓璁湪鏁存暟鍩熶娇鐢?
// 鍒ゆ柇鐐规槸鍚﹀湪绾挎涓?
// -1 鐐瑰湪绾挎绔偣 | 0 鐐逛笉鍦ㄧ嚎娈典笂 | 1 鐐逛弗鏍煎湪绾挎涓?
int is_on(const Point &p) const
{
if (p==a || p==b) return -1;
return (p-a).toleft(p-b)==0 && (p-a)*(p-b)<-eps;
}
// 鍒ゆ柇绾挎鐩寸嚎鏄惁鐩镐氦
// -1 鐩寸嚎缁忚繃绾挎绔偣 | 0 绾挎鍜岀洿绾夸笉鐩镐氦 | 1 绾挎鍜岀洿绾夸弗鏍肩浉浜?
int is_inter(const Line &l) const
{
if (l.toleft(a)==0 || l.toleft(b)==0) return -1;
return l.toleft(a)!=l.toleft(b);
}
// 鍒ゆ柇涓ょ嚎娈垫槸鍚︾浉浜?
// -1 鍦ㄦ煇涓€绾挎绔偣澶勭浉浜?| 0 涓ょ嚎娈典笉鐩镐氦 | 1 涓ょ嚎娈典弗鏍肩浉浜?
int is_inter(const Segment &s) const
{
if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
const Line l{a,b-a},ls{s.a,s.b-s.a};
return l.toleft(s.a)*l.toleft(s.b)==-1 && ls.toleft(a)*ls.toleft(b)==-1;
}
// 鐐瑰埌绾挎璺濈锛堝繀椤荤敤娴偣鏁帮級
T dis(const Point &p) const
{
if ((p-a)*(b-a)<-eps || (p-b)*(a-b)<-eps) return min(p.dis(a),p.dis(b));
const Line l{a,b-a};
return l.dis(p);
}
// 涓ょ嚎娈甸棿璺濈锛堝繀椤荤敤娴偣鏁帮級
T dis(const Segment &s) const
{
if (is_inter(s)) return 0;
return min({dis(s.a),dis(s.b),s.dis(a),s.dis(b)});
}
};
void run_case(){
T x, y, r, vx, vy;
cin >> x >> y >> r >> vx >> vy;
Point from = {x, y};
T lx, ly, rx, ry;
cin >> lx >> ly >> rx >> ry;
Point ld, lu, rd, ru;
if (rx-lx < 2 * r || ry-ly < 2 * r) {cout << "No"; return;}
ld = {lx+r, ly+r}; lu = {lx+r, ry-r};
rd = {rx-r, ly+r}; ru = {rx-r, ry-r};
Segment l1, l2, l3, l4;
l1 = {ld, rd}; l2 = {ld, lu};
l3 = {ru, rd}; l4 = {ru, lu};
Line input = {from, {vx, vy}};
if (input.ray_segment_intersection(input, ld, rd).first == 1) cout << "Yes";
else if (input.ray_segment_intersection(input, ld, lu).first == 1) cout << "Yes";
else if (input.ray_segment_intersection(input, ru, rd).first == 1) cout << "Yes";
else if (input.ray_segment_intersection(input, ru, lu).first == 1) cout << "Yes";
else cout << "No";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc = 1;
cin >> tc;
while (tc--)
{
run_case();
cout << '\n';
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
5 0 0 1 1 0 2 -2 6 2 0 0 1 1 0 2 0 6 2 0 0 1 1 1 1 1 3 3 0 0 1 -1 -1 1 1 3 3 0 0 1 -1 1 -5 -5 5 5
output:
Yes No Yes No Yes
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 0 0 1000000 1000000 1000000 -1000000 -1000000 1000000 1000000 1000000 1000000 1 -1000000 -1000000 -1000000 -1000000 -999999 -999999
output:
Yes No
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 12ms
memory: 3840kb
input:
10000 10 -10 10 1 -2 -13 -8 6 -1 -7 -10 3 3 1 -3 -12 14 -9 -9 -2 4 4 -3 -11 7 -8 12 -3 1 8 -1 0 -11 1 19 13 -1 8 9 -3 2 11 -5 17 4 -2 -7 3 -3 5 -12 -14 10 1 0 3 6 -5 3 -11 2 2 16 4 9 6 5 -4 -8 -11 18 -1 0 0 8 4 -2 -10 -15 1 12 8 4 4 5 2 -17 3 8 7 -3 7 10 -4 0 1 0 10 20 -6 -10 5 -3 -1 -20 -20 15 7 5 ...
output:
No No No No No Yes No No No No No Yes No Yes No No Yes No Yes No No No No No Yes No No No Yes No No No Yes No No Yes No No No No No No No No No No No No Yes No No No No No No No No No Yes Yes No No Yes Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes...
result:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 12ms
memory: 3712kb
input:
10000 435040 443595 65698 -909008 707638 -786096 -552413 -684992 853567 662291 -64591 243223 870386 898512 -302221 -384430 747067 -262550 -626562 -285970 945616 -695143 223635 14005 -632139 169681 481076 -955128 470568 284454 -511490 -623372 -465039 -713986 477856 -675726 304873 -693785 286659 -9272...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No Yes No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 10ms
memory: 3712kb
input:
10000 2 -1000000 1 0 1 -6 999998 1 1000000 0 -1000000 1 0 1 -3 999998 -1 999999 4 -1000000 1 0 1 -1 999996 6 999999 1 -1000000 1 0 -1 0 999998 2 999999 2 -1000000 1 0 1 -1 999997 4 999999 1 -1000000 1 0 1 -2 999998 2 1000000 -4 -1000000 1 0 1 -5 999997 -4 999999 -3 -1000000 1 0 1 -3 999996 -2 100000...
output:
No No Yes No Yes Yes No No No No No No No No No No No No No No No No No Yes No Yes No No No No No No Yes No No No No Yes No No No No No No No No No No No No No Yes No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No No Yes Yes No No No No No No Yes Yes No No No No No N...
result:
ok 10000 lines
Test #6:
score: 0
Accepted
time: 10ms
memory: 3840kb
input:
10000 -1000000 -2 1 1 0 999998 -6 1000000 6 -1000000 -5 1 -1 0 999996 -2 1000000 3 -1000000 2 1 1 0 999998 0 999999 4 -1000000 -5 1 -1 0 999997 0 999998 5 -1000000 -3 1 -1 0 999997 -7 1000000 -2 -1000000 0 1 -1 0 999996 4 999997 6 -1000000 -2 1 1 0 999998 3 999999 6 -1000000 -3 1 -1 0 999996 -3 1000...
output:
Yes No No No No No No No No Yes No No No No No No No Yes No No No No No No No No No No No Yes Yes No No No No No No No No Yes No No No No No No No No No Yes No No No No Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No Yes Yes No No No No No No Yes No No No No No Yes Ye...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 11ms
memory: 3712kb
input:
10000 -1000000 -1000000 39 2 0 19265 57834 60609 77684 -1000000 -1000000 22 -1 2 16667 94521 76708 97725 -1000000 -1000000 75 1 1 2120 9797 44577 47582 -1000000 -1000000 61 2 0 2400 15626 21867 21831 -1000000 -1000000 39 0 -1 32558 37142 66755 56056 -1000000 -1000000 64 1 2 33672 45285 53247 46521 -...
output:
No No Yes No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes Yes No No No No No No No No Yes No No No No No No No No Yes No No No No No No No No No Yes N...
result:
ok 10000 lines
Extra Test:
score: 0
Extra Test Passed