QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #418867 | #6734. Click the Circle | ericmegalovania | WA | 9ms | 3892kb | C++20 | 6.8kb | 2024-05-23 16:14:19 | 2024-05-23 16:14:19 |
Judging History
answer
#include<bits/stdc++.h>//大模拟
using namespace std;
#define ONLINE
#ifndef ONLINE
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) ;
#endif
using LL=long long;
using PII=pair<int,int>;
template<typename T>
inline T READ(){
T x=0; bool f=0; char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?-x:x;
}
inline int read(){return READ<int>();}
inline LL readLL(){return READ<LL>();}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const double eps=1e-8; //精度，可按需要增加至1e-12之类的
int sign(double x){ //符号函数
if(fabs(x)<eps) return 0;
if(x<0) return -1;
return 1;
}
int dcmp(double x,double y){ //比较函数
if(fabs(x-y)<eps) return 0;
if(x<y) return -1;
return 1;
}
using PDD=pair<double,double>;
#define x first
#define y second
//基本运算符重载
PDD operator +(PDD a,PDD b){return PDD{a.x+b.x,a.y+b.y};}
PDD operator -(PDD a,PDD b){return PDD{a.x-b.x,a.y-b.y};}
PDD operator *(double k,PDD a){return PDD{k*a.x,k*a.y};}
PDD operator *(PDD a,double k){return PDD{k*a.x,k*a.y};}
PDD operator /(PDD a,double k){return PDD{a.x/k,a.y/k};}
double dot(PDD a,PDD b){ //内积
return a.x*b.x+a.y*b.y;
}
double cross(PDD a,PDD b){ //叉积
return a.x*b.y-b.x*a.y;
}
//取模（长度）
double get_length(PDD a){
return sqrt(dot(a,a));
}
//计算向量夹角
double get_angle(PDD a,PDD b){
return acos(dot(a,b)/get_length(a)/get_length(b));
}
//计算两个向量构成的平行四边形的面积
double area(PDD a,PDD b,PDD c){
return cross(b-a,c-a);
}
//A绕原点**顺时针**旋转angle（弧度制）
PDD rotate(PDD a,double angle){
return PDD{a.x*cos(angle) + a.y*sin(angle),
-a.x*sin(angle) + a.y*cos(angle)};
}
//取直线p+vt, q+wt的交点
//cross(v,w)==0 则两直线平行或者重合，注意特判，这里没加特判
PDD get_line_inter(PDD p, PDD v, PDD q, PDD w){
PDD u = p - q;
double t = cross(w, u) / cross(v, w);
return p + v * t;
}
//点p; 直线由a, b两点表示
//点到直线的距离
double dis2line(PDD p, PDD a, PDD b){
PDD v1 = b - a, v2 = p - a;
return fabs(cross(v1, v2) / get_length(v1));
}
//点到线段的距离
double dis2seg(PDD p, PDD a, PDD b){
if (a == b) return get_length(p - a);
PDD v1 = b - a, v2 = p - a, v3 = p - b;
if (sign(dot(v1, v2)) < 0) return get_length(v2);
if (sign(dot(v1, v3)) > 0) return get_length(v3);
return dis2line(p, a, b);
}
//点在直线上的投影
PDD get_line_proj(PDD p, PDD a, PDD b){
PDD v = b - a;
return a + v * (dot(v, p - a) / dot(v, v));
}
//点是否在线段上
bool on_seg(PDD p, PDD a, PDD b){
return sign(cross(p - a, p - b)) == 0 && sign(dot(p - a, p - b)) <= 0;
}
//判断两线段是否相交
bool seg_inter(PDD a1, PDD a2, PDD b1, PDD b2){
double c1 = cross(a2-a1, b1-a1), c2 = cross(a2-a1, b2-a1);
double c3 = cross(b2-b1, a1-b1), c4 = cross(b2-b1, a2-b1);
// 有if则允许线段在端点处相交，无if则不允许，根据需要添加
if(!sign(c1) && !sign(c2) && !sign(c3) && !sign(c4)){
bool f1 = on_seg(b1, a1, a2);
bool f2 = on_seg(b2, a1, a2);
bool f3 = on_seg(a1, b1, b2);
bool f4 = on_seg(a2, b1, b2);
bool f = (f1|f2|f3|f4);
return f;
}
return (sign(c1)*sign(c2) < 0 && sign(c3)*sign(c4) < 0);
}
//计算**任意**多边形面积（不一定凸）
double polygon_area(vector<PDD>p){
double s = 0;
for (int i = 1; i + 1 < p.size(); i ++ )
s += cross(p[i] - p[0], p[i + 1] - p[i]);
return s / 2;
}
double R; //R=2r
//判断滑条和滑条是否相交
bool check1(PDD a,PDD b,PDD c,PDD d){
if(seg_inter(a,b,c,d)) return 1;
double dis=min({dis2seg(a,c,d),dis2seg(b,c,d),dis2seg(c,a,b),dis2seg(d,a,b)});
return dcmp(dis,R)<=0;
}
//判断圆圈和滑条是否相交
bool check2(PDD p,PDD a,PDD b){
return dcmp(dis2seg(p,a,b),R)<=0;
}
//返回滑条在[s,t]时间内的线段
pair<PDD,PDD>get(int s,int t,array<int,6>u){
s=max(s,u[4]);
t=min(t,u[5]);
double sp,tp;//s_proportion, t_proportion
sp=1.0*(s-u[4])/(u[5]-u[4]);
tp=1.0*(t-u[4])/(u[5]-u[4]);
PDD p0={u[0],u[1]},vec={u[2]-u[0],u[3]-u[1]};
return {p0+sp*vec,p0+tp*vec};
}
int main(){
int n=read(),r=read(),d=read(); R=2.0*r;
vector<array<int,3>>a;
vector<array<int,6>>b;
for(int i=1;i<=n;i++){
if(read()==1){
static array<int,3>u;
u[0]=read(),u[1]=read(),u[2]=read();
a.push_back(u);
}
else{
static array<int,6>u;
u[0]=read(),u[1]=read(),u[2]=read(),
u[3]=read(),u[4]=read(),u[5]=read();
b.push_back(u);
}
}
const int t_inf=1e4+1;
int ans=b.size();
for(int i=0;i<a.size();i++){
for(int j=i+1;j<a.size();j++){
int tl,tr;
tl=max({a[i][2]-d,a[j][2]-d});
tr=min({a[i][2]+d,a[j][2]+d});
if(tl>tr) continue;
//circle & circle
int dx=a[i][0]-a[j][0],dy=a[i][1]-a[j][1];
if(1ll*dx*dx+1ll*dy*dy<=4ll*r*r) ans++;
}
}
for(int i=0;i<b.size();i++){
for(int j=i+1;j<b.size();j++){
int tl,tr;
tl=max({b[i][4]-d,b[j][4]-d});
tr=min({b[i][5]+d,b[j][5]+d});
if(tl>tr) continue;
//slide & slide
ans+=check1({b[i][0],b[i][1]},{b[i][2],b[i][3]},{b[j][0],b[j][1]},{b[j][2],b[j][3]});
//k-circle & slide
auto [Si,Ti]=get(tl,tr,b[i]);
ans+=check1(Si,Ti,{b[j][0],b[j][1]},{b[j][2],b[j][3]});
auto [Sj,Tj]=get(tl,tr,b[j]);
ans+=check1(Sj,Tj,{b[i][0],b[i][1]},{b[i][2],b[i][3]});
//k-circle & k-circle
PDD delta_s=Si-Sj,delta_vec=((Ti-Si)-(Tj-Sj));
static auto calc=[&](double x)->double{
//(Si+veci*x)-(Sj+vecj*x)
return get_length(delta_s+delta_vec*x);
};
debug("Si(%.3lf,%.3lf) Ti(%.3lf,%.3lf) Sj(%.3lf,%.3lf) Tj(%.3lf,%.3lf)\n",
Si.first,Si.second,Ti.first,Ti.second,Sj.first,Sj.second,Tj.first,Tj.second);
debug("delta_s=(%.3lf,%.3lf) delta_vec=(%.3lf,%.3lf)\n",
delta_s.first,delta_s.second,delta_vec.first,delta_vec.second);
double l=0,r=1,mid,lmid,rmid,fl,fr,dis=1e5;
while(r-l>eps){
mid=(l+r)/2;
lmid=mid-eps,rmid=mid+eps;
fl=calc(lmid),fr=calc(rmid);
if(fl<fr) r=mid;
else l=mid;
debug("f(%.3lf)=%.12lf f(%.3lf)=%.12lf\n",lmid,fl,rmid,fr);
dis=min({dis,fl,fr});
}
debug("i=%d j=%d dis=%.12lf\n",i,j,dis);
ans+=(dcmp(dis,R)<=0);
}
}
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
int tl,tr;
tl=max({a[i][2]-d,b[j][4]-d});
tr=min({a[i][2]+d,b[j][5]+d});
if(tl>tr) continue;
//circle & slide
ans+=check2({a[i][0],a[i][1]},{b[j][0],b[j][1]},{b[j][2],b[j][3]});
//circle & k-circle
auto [S,T]=get(tl,tr,b[j]);
ans+=check2({a[i][0],a[i][1]},S,T);
}
}
printf("%d",ans);
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 3744kb
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: 3728kb
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: 3892kb
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: 3792kb
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: 9ms
memory: 3824kb
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:
22811
result:
wrong answer 1st numbers differ - expected: '22721', found: '22811'