QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#193197#7521. Find the Gapucup-team918#WA 1ms5824kbC++174.7kb2023-09-30 16:35:112023-09-30 16:35:12

Judging History

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

  • [2023-09-30 16:35:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5824kb
  • [2023-09-30 16:35:11]
  • 提交

answer

//Was yea ra,rra yea ra synk sphilar yor en me exec hymme METAFALICA waath!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define ull unsigned ll
#define lowbit(x) (x&(-x))
#define djq 998244353
const short sint=0x3f3f;
const int inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
const double alpha=0.73;
const double PI=acos(-1);
inline void file(){
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
}
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<20)+5,stdin),p1==p2)?EOF:*p1++;
}
//#define getc getchar
inline ll read(){
	rg ll ret=0,f=0;char ch=getc();
    while(!isdigit(ch)){if(ch==EOF)exit(0);if(ch=='-')f=1;ch=getc();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getc();}
    return f?-ret:ret;
}
inline int rdstr(char* s){
	char ch=getc(); int len(0);
	while(ch<33||ch>126) ch=getc();
	while(ch>=33&&ch<=126) (*s++)=ch,++len,ch=getc();
	return len;
}
#define ep emplace
#define epb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define it iterator
#define mkp make_pair
#define naive return 0*puts("Yes")
#define angry return 0*puts("No")
#define fls fflush(stdout)
#define rep(i,a) for(rg int i=1;i<=a;++i)
#define per(i,a) for(rg int i=a;i;--i)
#define rep0(i,a) for(rg int i=0;i<=a;++i)
#define per0(i,a) for(rg int i=a;~i;--i)
#define szf sizeof
typedef vector<int> vec;
typedef pair<int,int> pii;
struct point{ int x,y; point(int x=0,int y=0):x(x),y(y) {} inline bool operator<(const point& T)const{ return x^T.x?x<T.x:y<T.y; }; };
inline int ksm(int base,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*base%djq;base=1ll*base*base%djq,p>>=1;}return ret;}
inline void pls(int& x,const int k){ x=(x+k>=djq?x+k-djq:x+k); }
inline int add(const int a,const int b){ return a+b>=djq?a+b-djq:a+b; }
inline void sub(int& x,const int k){ x=(x-k<0?x-k+djq:x-k); }
inline int inc(const int a,const int b){ return a<b?a-b+djq:a-b; }
inline void ckmn(int& x,const int k){ x=(k<x?k:x); }
inline void ckmx(int& x,const int k){ x=(k>x?k:x); }
inline void ckmn(ll& x,const ll k){ x=(k<x?k:x); }
inline void ckmx(ll& x,const ll k){ x=(k>x?k:x); }
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define double long double
const double eps=1e-16;
#define Vector Point
inline int dcmp(double a){return a<-eps?-1:(a>eps?1:0); }
inline double Abs(double a){return a*dcmp(a);}
double reps(){return (1.*(rnd()%98)/97-.5)*eps;}
struct Point{
	double x,y,z;
	void shake(){x+=reps(),y+=reps(),z+=reps();}	
	Point(double x=0,double y=0,double z=0):x(x),y(y),z(z) {}
}p[55];
inline Vector operator+(Vector a,Vector b){ return Vector(a.x+b.x,a.y+b.y,a.z+b.z); }
inline Vector operator-(Vector a,Vector b){ return Vector(a.x-b.x,a.y-b.y,a.z-b.z); }
inline Vector operator*(Vector a,double b){ return Vector(a.x*b,a.y*b,a.z*b); }
inline Vector operator/(Vector a,double b){ return Vector(a.x/b,a.y/b,a.z/b); }
inline double Dot(Point a,Point b){ return a.x*b.x+a.y*b.y+a.z*b.z; }
inline double Len(Point a){ return sqrt(Dot(a,a)); }
inline Point Cro(Point a,Point b){ return Point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x); }
struct face{
	int v[3];
	inline Point area(){ return Cro(p[v[1]]-p[v[0]],p[v[2]]-p[v[0]]); }
	inline bool check(int x){ return Dot(p[x]-p[v[0]],area())>0?1:0; }
};
int n;
bool flag,vis[2005][2005];
vector<face> cur; 
double ans;
inline void solve(){
	cur.clear();
	cur.push_back((face){1,2,3});
	cur.push_back((face){3,2,1});
	for(rg int i=4;i<=n;++i){
		vector<face> tmp;
		for(rg int j=0;j<cur.size();++j){
			face now=cur[j];
			int checker=now.check(i);
			if(!checker) tmp.epb(now);
			for(rg int k=0;k<3;++k){
				vis[now.v[k]][now.v[(k+1)%3]]=checker;
			}
		}
		for(rg int j=0;j<cur.size();++j){
			for(rg int k=0;k<3;++k){
				int now=cur[j].v[k],nex=cur[j].v[(k+1)%3];
				if(vis[now][nex]!=vis[nex][now]&&vis[now][nex]){
					tmp.push_back((face){now,nex,i});
				}
			}
		}
		cur=tmp;
	}
}
signed main(){
	//file();
	n=read();
	rep(i,n) p[i].x=read(),p[i].y=read(),p[i].z=read(),p[i].shake();
	solve(); double ans=1e9;
	for(rg int i=0;i<cur.size();++i){
		Point a=p[cur[i].v[0]],b=p[cur[i].v[1]],c=p[cur[i].v[2]];
		//printf("(%.3lf,%.3lf,%.3lf) (%.3lf,%.3lf,%.3lf) (%.3lf,%.3lf,%.3lf)\n",a.x,a.y,a.z,b.x,b.y,b.z,c.x,c.y,c.z);
		double ar=Len(Cro(b-a,c-a)),mx(0);
		rep(i,n){
			double nw=Dot(p[i]-a,Cro(b-a,c-a))/Len(Cro(b-a,c-a));
			mx=max(mx,fabs(nw));
		}
		ans=min(ans,mx);
	}
	printf("%.12Lf\n",ans);
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5824kb

input:

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

output:

1.000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5756kb

input:

5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1

output:

0.707106781187

result:

ok found '0.707106781', expected '0.707106781', error '0.000000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 5704kb

input:

50
973 1799 4431
1036 1888 4509
1099 1977 4587
1162 2066 4665
1225 2155 4743
1288 2244 4821
1351 2333 4899
1414 2422 4977
1540 2600 5133
1603 2689 5211
1666 2778 5289
1729 2867 5367
1792 2956 5445
1855 3045 5523
1918 3134 5601
1981 3223 5679
2044 3312 5757
2107 3401 5835
2170 3490 5913
2296 3668 606...

output:

1000000000.000000000000

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '1000000000.0000000', error = '1000000000.0000000'