QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#819185#4418. Laser AlarmKevin5307AC ✓698ms3784kbC++232.4kb2024-12-18 13:47:002024-12-18 13:47:00

Judging History

你现在查看的是最新测评结果

  • [2024-12-18 13:47:00]
  • 评测
  • 测评结果:AC
  • 用时:698ms
  • 内存:3784kb
  • [2024-12-18 13:47:00]
  • 提交

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;
}

詳細信息

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