QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#819185 | #4418. Laser Alarm | Kevin5307 | AC ✓ | 698ms | 3784kb | C++23 | 2.4kb | 2024-12-18 13:47:00 | 2024-12-18 13:47:00 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define ld long double
void die(string S){puts(S.c_str());exit(0);}
struct p3
{
ld x,y,z;
ld norm() const {return x*x+y*y+z*z;}
ld abs() const {return sqrtl(norm());}
};
p3 operator +(p3 x,p3 y){return {x.x+y.x,x.y+y.y,x.z+y.z};}
p3 operator -(p3 x,p3 y){return {x.x-y.x,x.y-y.y,x.z-y.z};}
p3 operator *(p3 x,ld y){return {x.x*y,x.y*y,x.z*y};}
p3 operator /(p3 x,ld y){return {x.x/y,x.y/y,x.z/y};}
p3 operator *(p3 x,p3 y)
{
return {
x.y*y.z-x.z*y.y,
x.z*y.x-x.x*y.z,
x.x*y.y-x.y*y.x
};
}
ld operator %(p3 x,p3 y){return x.x*y.x+x.y*y.y+x.z*y.z;}
struct plane
{
p3 n;
ld d;
plane(){}
plane(p3 a,p3 b,p3 c):n((c-a)*(b-a)){d=n%a;}
ld side(p3 x) const {return n%x-d;}
};
p3 A[55],B[55];
const ld eps=1e-9;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i].x>>A[i].y>>A[i].z;
cin>>B[i].x>>B[i].y>>B[i].z;
}
vector<p3> vec;
for(int i=1;i<=n;i++)
{
vec.pb(A[i]);
vec.pb(B[i]);
}
int ans=1;
for(int i=0;i<sz(vec);i++)
for(int j=i+1;j<sz(vec);j++) if((vec[i]-vec[j]).norm()>eps)
for(int k=j+1;k<sz(vec);k++) if((vec[i]-vec[k]).norm()>eps) if((vec[k]-vec[j]).norm()>eps) if(((vec[i]-vec[j])*(vec[j]-vec[k])).norm()>eps)
{
plane P(vec[i],vec[j],vec[k]);
int cnt=0;
for(int i=1;i<=n;i++)
{
ld x=P.side(A[i]);
ld y=P.side(B[i]);
if(x>y) swap(x,y);
if(x<eps&&y>-eps) cnt++;
}
ans=max(ans,cnt);
}
for(int i=0;i<sz(vec);i++)
for(int j=i+1;j<sz(vec);j++)
{
int cnt=0;
for(int a=1;a<=n;a++)
if(((vec[i]-vec[j])*(vec[j]-A[a])).norm()<eps||((vec[i]-vec[j])*(vec[j]-B[a])).norm()<eps)
cnt++;
ans=max(ans,cnt);
}
cout<<ans<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 698ms
memory: 3784kb
input:
10 50 94 57 39 12 69 59 86 46 44 17 32 83 35 86 71 47 41 50 68 93 71 54 28 25 92 74 2 30 60 86 87 52 54 32 17 88 51 63 96 23 12 69 1 82 85 20 9 90 25 72 42 49 4 52 30 86 94 93 43 34 10 45 30 85 32 75 84 37 71 37 78 19 28 30 7 40 10 77 5 68 86 83 3 41 71 73 8 86 69 48 65 11 6 49 64 50 61 2 24 60 11 9...
output:
33 39 36 36 40 37 34 33 50 50
result:
ok 10 lines