QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #397390 | #6734. Click the Circle | wtz2333 | WA | 24ms | 3952kb | C++20 | 13.8kb | 2024-04-24 01:11:01 | 2024-04-24 01:11:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr double eps = 1e-12;
constexpr double PI = acos(-1);
constexpr double inf = 1e9;
struct Point {
double x, y;
}; // 点
using Vec = Point; // 向量
struct Line { Point P; Vec v; }; // 直线（点向式），射线时为A->B
struct Seg {
Point A, B;
}; // 线段（存两个端点）
struct Circle { Point O; double r; }; // 圆（存圆心和半径）
using Points = std::vector<Point>;
using ConvexHull = std::vector<Point>;
const Point O = {0, 0}; // 原点
const Line Ox = {O, {1, 0}}, Oy = {O, {0, 1}}; // 坐标轴
bool eq(double a, double b) { return abs(a - b) < eps; } // ==
bool gt(double a, double b) { return a - b > eps; } // >
bool lt(double a, double b) { return a - b < -eps; } // <
bool ge(double a, double b) { return a - b > -eps; } // >=
bool le(double a, double b) { return a - b < eps; } // <=
Vec operator + (const Vec &a,const Vec &b){return (Vec){a.x + b.x,a.y + b.y};}
Vec operator - (const Vec &a,const Vec &b){return (Vec){a.x - b.x,a.y - b.y};}
Vec operator * (const Vec &a,const double &b){return (Vec){b * a.x,b * a.y};}
Vec operator * (const double &a,const Vec &b){return (Vec){a * b.x,a * b.y};}
Vec operator / (const Vec &a,const double &b){return (Vec){a.x / b,a.y / b};}
double operator * (const Point &a,const Point &b){return a.x * b.x + a.y * b.y;}// dot // 点乘
double operator ^ (const Point &a,const Point &b){return a.x * b.y - a.y * b.x;}// cross // 叉乘
bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
double len(const Vec &a){return sqrt(a * a);}
ll cross(Point a,Point b){return (ll)a.x * (ll)b.y - (ll)a.y * (ll)b.x;}
ll dot(Point a,Point b){return (ll)a.x * (ll)b.x + (ll)a.y * (ll)b.y;}
double angle(const Vec &a,const Vec &b){return acos(a * b / len(a)/len(b));}
double Polar_angle(Vec &v){return atan2(v.y,v.x);}
int sgn(double x){
if(fabs(x) < eps)
return 0;
if(x < 0)
return -1;
return 1;
}
Vec r90a(Vec v) { return {-v.y, v.x}; } // 逆时针旋转90度的向量
Vec r90c(Vec v) { return {v.y, -v.x}; } // 顺时针旋转90度的向量
// 两向量的夹角余弦
// DEPENDS len, V*V
double cos_t(Vec u, Vec v) { return u * v / len(u) / len(v); }
// 归一化向量（与原向量方向相同的单位向量）
// DEPENDS len
Vec norm(Vec v) { return {v.x / len(v), v.y / len(v)}; }
// 与原向量平行且横坐标大于等于0的单位向量
// DEPENDS d*V, len
Vec pnorm(Vec v) { return (v.x < 0 ? -1 : 1) / len(v) * v; }
// 线段的方向向量
// DEPENDS V-V
// NOTE 直线的方向向量直接访问属性v
Vec dvec(Seg l) { return l.B - l.A; }
//----------------------------------------------------------//
Line line(Point A, Point B) { return {A, B - A}; }
// 斜截式直线
Line line(double k, double b) { return {{0, b}, {1, k}}; }
// 点斜式直线
Line line(Point P, double k) { return {P, {1, k}}; }
// 线段所在直线
// DEPENDS V-V
Line line(Seg l) { return {l.A, l.B - l.A}; }
// 给定直线的横坐标求纵坐标
// NOTE 请确保直线不与y轴平行
double at_x(Line l, double x) { return l.P.y + (x - l.P.x) * l.v.y / l.v.x; }
// 给定直线的纵坐标求横坐标
// NOTE 请确保直线不与x轴平行
double at_y(Line l, double y) { return l.P.x - (y + l.P.y) * l.v.x / l.v.y; }
// 点到直线的垂足
// DEPENDS V-V, V*V, d*V
Point pedal(Point P, Line l) { return l.P - (l.P - P) * l.v / (l.v * l.v) * l.v; }
// 过某点作直线的垂线
// DEPENDS r90c
Line perp(Line l, Point P) { return {P, r90c(l.v)}; }
// 角平分线
// DEPENDS V+V, len, norm
Line bisec(Point P, Vec u, Vec v) { return {P, norm(u) + norm(v)}; }
//seg------------------------------------------//
// 线段的方向向量
// DEPENDS V-V
// NOTE 直线的方向向量直接访问属性v
//Vec dvec(Seg l) { return l.B - l.A; }
// 线段中点
Point midp(Seg l) { return {(l.A.x + l.B.x) / 2, (l.A.y + l.B.y) / 2}; }
// 线段中垂线
// DEPENDS r90c, V-V, midp
Line perp(Seg l) { return {midp(l), r90c(l.B - l.A)}; }
//----------------------------------------------------------------//
// 向量是否互相垂直
// DEPENDS eq, V*V
bool verti(Vec u, Vec v) { return eq(u * v, 0); }
// 向量是否互相平行
// DEPENDS eq, V^V
bool paral(Vec u, Vec v) { return eq(u ^ v, 0); }
// 向量是否与x轴平行
// DEPENDS eq
bool paral_x(Vec v) { return eq(v.y, 0); }
// 向量是否与y轴平行
// DEPENDS eq
bool paral_y(Vec v) { return eq(v.x, 0); }
// 点是否在直线上
// DEPENDS eq
bool on(Point P, Line l) { return eq((P.x - l.P.x) * l.v.y, (P.y - l.P.y) * l.v.x); }
// 点是否在射线上
// DEPENDS eq
bool on_ray(Point P, Line l) { return on(P,l) && ((P - l.P) * l.v) >= 0; }
// 点是否在线段上
// DEPENDS eq, len, V-V
bool on(Point P, Seg l) { return eq(len(P - l.A) + len(P - l.B), len(l.A - l.B)); }
// 两个点是否重合
// DEPENDS eq
bool operator==(Point A, Point B) { return eq(A.x, B.x) && eq(A.y, B.y); }
// 两条直线是否重合
// DEPENDS eq, on(L)
bool operator==(Line a, Line b) { return on(a.P, b) && on(a.P + a.v, b); }
// 两条线段是否重合
// DEPENDS eq, P==P
bool operator==(Seg a, Seg b) { return (a.A == b.A && a.B == b.B) || (a.A == b.B && a.B == b.A); }
// 以横坐标为第一关键词、纵坐标为第二关键词比较两个点
// DEPENDS eq, lt
//bool operator<(Point A, Point B) { return lt(A.x, B.x) || (eq(A.x, B.x) && lt(A.y, B.y)); }
// 直线与圆是否相切
// DEPENDS eq, V^V, len
bool tangency(Line l, Circle C) { return eq(abs((C.O ^ l.v) - (l.P ^ l.v)), C.r * len(l.v)); }
// 圆与圆是否相切
// DEPENDS eq, V-V, len
bool tangency(Circle C1, Circle C2) { return eq(len(C1.O - C2.O), C1.r + C2.r); }
//--------------------------------------------------//
// 两点间的距离
// DEPENDS len, V-V
double dis(Point A, Point B) { return len(A - B); }
// 点到直线的距离
// DEPENDS V^V, len
double dis(Point P, Line l) { return abs((P ^ l.v) - (l.P ^ l.v)) / len(l.v); }
// 点到线段的距离
double dis(Point P,Seg l) {
// cerr << "ASDfasdfasd\n";
if(fabs((P - l.A) * (l.B - l.A)) < eps || fabs((P - l.B) * (l.A - l.B)) < eps){
// cerr << "!!!asdafd\n";
return min(dis(P,l.A),dis(P,l.B));
}else {
Line l1 = line(l);
return dis(P,l1);
}
}
// 平行直线间的距离
// DEPENDS d*V, V^V, len, pnorm
// NOTE 请确保两直线是平行的
double dis(Line a, Line b) { return abs((a.P ^ pnorm(a.v)) - (b.P ^ pnorm(b.v))); }
// 平移
// DEPENDS V+V
Line operator+(Line l, Vec v) { return {l.P + v, l.v}; }
Seg operator+(Seg l, Vec v) { return {l.A + v, l.B + v}; }
// 旋转 逆时针
// DEPENDS V+V, V-V
Point rotate(Point P, double rad) { return {cos(rad) * P.x - sin(rad) * P.y, sin(rad) * P.x + cos(rad) * P.y}; }
Point rotate(Point P, double rad, Point C) { return C + rotate(P - C, rad); } // DEPENDS ^1
Line rotate(Line l, double rad, Point C = O) { return {rotate(l.P, rad, C), rotate(l.v, rad)}; } // DEPENDS ^1, ^2
Seg rotate(Seg l, double rad, Point C = O) { return {rotate(l.A, rad, C), rotate(l.B, rad, C)}; } // DEPENDS ^1, ^2
// 直线与直线交点
// DEPENDS eq, d*V, V*V, V+V, V^V
Points inter(Line a, Line b){
double c = a.v ^ b.v;
if (eq(c, 0)) {return {};}
Vec v = 1 / c * Vec{a.P ^ (a.P + a.v), b.P ^ (b.P + b.v)};
return {{v * Vec{-b.v.x, a.v.x}, v * Vec{-b.v.y, a.v.y}}};
}
// 线段与线段是否相交
bool cross_seg(Seg A,Seg B){
Point a = A.A,b = A.B,c = B.A,d = B.B;
double c1 = (b - a) ^ (c - a),c2 = (b - a) ^ (d - a);
double d1 = (d - c) ^ (a - c),d2 = (d - c) ^ (b - c);
return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;
}
int main() {
int n,d,R;
cin >> n >> R >> d;
vector<pair<Point,int>> C;
vector<tuple<Seg,int,int>> S;
int ans = 0;
for(int i = 0;i < n;i ++) {
int opt;
cin >> opt;
if(opt == 1) {
double x,y;
int t;
cin >> x >> y >> t;
C.push_back({Point{x,y},t});
}else {
Point s,t;
int u,v;
cin >> s.x >> s.y >> t.x >> t.y >> u >> v;
S.push_back(make_tuple(Seg{s,t},u,v));
ans ++;
}
}
for(int i = 0;i < C.size();i ++) {
for(int j = i + 1;j < C.size();j ++) {
auto [c1,t1] = C[i];
auto [c2,t2] = C[j];
int l = max(t1 - d,t2 - d);
int r = min(t1 + d,t2 + d);
if(l > r) continue;
double D = dis(c1,c2);
// cerr << D - 2.0 * R << endl;
if(D - 2.0 * R < eps) {
ans ++;
}
}
}// C - C
for(auto [c,t]:C) {
for(auto [s,u,v]:S) {
int l = min(t - d,u - d);
int r = max(t + d,v + d);
if(l > r)continue;
double D = dis(c,s);
if(D - 2.0 * R < eps) {
ans ++;
}
}
} // C - S.f
auto disss = [&](Seg a,Seg b) {
if(cross_seg(a,b)) return 0.0;
double D = min({dis(a.A,b),dis(a.B,b),dis(b.A,a),dis(b.B,a)});
return D;
};
for(int i = 0;i < S.size();i ++) {
auto [s1,u1,v1] = S[i];
for(int j = i + 1;j < S.size();j ++) {
auto [s2,u2,v2] = S[j];
int l = max(u1 - d,u2 - d);
int r = min(v1 + d,v2 + d);
if(l > r) continue;
double D = disss(s1,s2);
if(D - 2.0 * R < eps) {
ans ++;
}
}
}// S.f - S.f
auto check0 = [&](Seg s1,int u1,int v1,Seg s2,int u2,int v2) {
int l,r;
l = max(u1 - d,u2);
r = min(v1 + d,v2);
if(l <= r) {
Seg tmp2;
tmp2.A = s2.A + (s2.B - s2.A) * (l - u2) / (v2 - u2);
tmp2.B = s2.A + (s2.B - s2.A) * (r - u2) / (v2 - u2);
double D = disss(s1,tmp2);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(u1 - d,u2 - d);
r = min(v1 + d,u2);
if(l <= r) {
double D = dis(s2.A,s1);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(u1 - d,v2);
r = min(v1 + d,v2 + d);
if(l <= r) {
double D = dis(s2.B,s1);
if(D - 2.0 * R < eps) {
return true;
}
}
return false;
};
for(int i = 0;i < S.size();i ++) {
auto [s1,u1,v1] = S[i];
for(int j = 0;j < S.size();j ++) {
if(j == i) continue;
auto [s2,u2,v2] = S[j];
if(check0(s1,u1,v1,s2,u2,v2)) {
ans ++;
}
}
}// S.f - S.C
auto check1 = [&](Point c,int t,Seg s,int u,int v) {
int l,r;
l = max(t - d,u - d);
r = min(t + d,u);
if(l <= r) {
double D = dis(c,s.A);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(t - d,v);
r = min(t + d,v + d);
if(l <= r) {
double D = dis(c,s.B);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(t - d,u);
r = max(t + d,v);
if(l <= r) {
Seg tmp;
tmp.A = s.A + (s.B - s.A) * (l - u) / (v - u);
tmp.B = s.A + (s.B - s.A) * (r - u) / (v - u);
double D = dis(c,tmp);
if(D - 2.0 * R < eps) {
return true;
}
}
return false;
};
for(auto [c,t]:C) {
for(auto [s,u,v]:S) {
if(check1(c,t,s,u,v)) {
ans ++;
}
}
}// C - S.C
// cerr << "asdfasdf\n";
auto check2 = [&](Seg s1,int u1,int v1,Seg s2,int u2,int v2) {
int l,r;
l = max(u1 - d,u2 - d);
r = min(u1,u2);
if(l <= r) {
double D = dis(s1.A,s2.A);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(v1,v2);
r = min(v1 + d,v2 + d);
if(l <= r) {
double D = dis(s1.B,s2.B);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(u1 - d,v2);
r = min(u1,v2 + d);
if(l <= r) {
double D = dis(s1.A,s2.B);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(v1,u2 - d);
r = min(v1 + d,u2);
if(l <= r) {
double D = dis(s1.B,s2.A);
if(D - 2.0 * R < eps) {
return true;
}
}
l = max(u1,u2);
r = min(v1,v2);
if(l <= r){
Seg tmp1;
tmp1.A = s1.A + (s1.B - s1.A) * (l - u1) / (v1 - u1);
tmp1.B = s1.A + (s1.B - s1.A) * (r - u1) / (v1 - u1);
Seg tmp2;
tmp2.A = s2.A + (s2.B - s2.A) * (l - u2) / (v2 - u2);
tmp2.B = s2.A + (s2.B - s2.A) * (r - u2) / (v2 - u2);
Seg tmp = {tmp1.A - tmp2.A,tmp1.B - tmp2.B};
double D = dis(O,tmp);
if(D - 2.0 * R < eps) {
return true;
}
}
return false;
};
for(int i = 0;i < S.size();i ++) {
auto [s1,u1,v1] = S[i];
for(int j = i + 1;j < S.size();j ++) {
auto [s2,u2,v2] = S[j];
if(check2(s1,u1,v1,s2,u2,v2)) {
ans ++;
}
}
}// S.C - S.C
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
input:
2 1 1 1 1 1 2 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
2 1 1 1 1 1 2 1 3 2 3
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 1 1 1 3 3 2 2 5 5 5 1 2 4
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 1 1 2 1 1 1 5 2 4 2 5 5 5 1 2 4
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 1 1 2 10 1 10 20 2 4 2 1 10 20 10 2 4
output:
6
result:
ok 1 number(s): "6"
Test #6:
score: -100
Wrong Answer
time: 24ms
memory: 3952kb
input:
1000 8 4 1 8323 2820 943 1 8246 2850 944 1 8177 2880 941 1 8154 2866 944 2 8325 8146 2865 2846 943 944 1 8349 2891 939 2 8176 8344 2888 2692 940 945 1 8191 2732 945 1 8144 2668 945 2 8182 8191 2889 2844 939 940 1 8173 2687 941 1 8241 2870 945 2 8266 8344 2910 2667 942 943 1 8169 2863 939 1 8349 2921...
output:
32916
result:
wrong answer 1st numbers differ - expected: '22721', found: '32916'