QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362475#8505. Almost Aligneducup-team052#WA 1ms8040kbC++232.7kb2024-03-23 15:41:272024-03-23 15:41:29

Judging History

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

  • [2024-03-23 15:41:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8040kb
  • [2024-03-23 15:41:27]
  • 提交

answer

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define pb push_back
using namespace std;
const int N=1000005;
int n;
struct node{
	int x,y,vx,vy;
}a[N];
struct vec{
	int x,vx,id;
}b[N];
vector<pair<double,int> >A[4];
int st[N],top;
double getT(const vec&u,const vec&v){
	return -1.*(v.x-u.x)/(v.vx-u.vx);
}
void solve(vector<pair<double,int> >&A){
	sort(b+1,b+n+1,[&](const vec&lhs,const vec&rhs){return lhs.vx!=rhs.vx?lhs.vx>rhs.vx:lhs.x>rhs.x;});
	st[top=1]=1;
	rep(i,2,n)if(b[i].x>b[st[top]].x&&b[i].vx<b[st[top]].vx){
		while(top>1&&getT(b[st[top-1]],b[st[top]])<getT(b[st[top]],b[i])){
			--top;
		}
		st[++top]=i;
	}
	reverse(st+1,st+top+1);
	A.emplace_back(0,b[st[1]].id);
	rep(i,1,top-1){
		A.emplace_back(getT(b[st[i]],b[st[i+1]]),b[st[i+1]].id);
	}
}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	cin>>n;
	rep(i,1,n){
		cin>>a[i].x>>a[i].y>>a[i].vx>>a[i].vy;
	}
	rep(i,1,n)b[i].x=a[i].x,b[i].vx=a[i].vx,b[i].id=i;
	solve(A[0]);
	rep(i,1,n)b[i].x=-a[i].x,b[i].vx=-a[i].vx,b[i].id=i;
	solve(A[1]);
	rep(i,1,n)b[i].x=a[i].y,b[i].vx=a[i].vy,b[i].id=i;
	solve(A[2]);
	rep(i,1,n)b[i].x=-a[i].y,b[i].vx=-a[i].vy,b[i].id=i;
	solve(A[3]);
	int p[4]={0,0,0,0};
	double l=0;
	double ans=1e100;
	auto calc=[&](int u1,int u2,int u3,int u4,double l,double r){
		int X=a[u1].x-a[u2].x;
		int VX=a[u1].vx-a[u2].vx;
		int Y=a[u3].y-a[u4].y;
		int VY=a[u3].vy-a[u4].vy;
		
		double a=VX*VY;
		double b=VX*Y+VY*X;
		double c=X*Y;
#define F(x) (a*(x)*(x)+b*(x)+c)
		double ret=min(F(l),F(r));
		double x0=-b/(a*2.);
		if(x0>=l&&x0<=r){
			ret=min(ret,F(x0));
		}
		return ret;
	};
	while(1){
		double r=1e100;
		int x=-1;
		rep(i,0,3){
			if(p[i]+1<SZ(A[i])&&(x==-1||A[i][p[i]+1].first<r)){
				r=A[i][p[i]+1].first;
				x=i;
			}
		}
		if(x==-1){
			ans=min(ans,calc(A[0][p[0]].second,A[1][p[1]].second,A[2][p[2]].second,A[3][p[3]].second,l,1e9));
			break;
		}
		ans=min(ans,calc(A[0][p[0]].second,A[1][p[1]].second,A[2][p[2]].second,A[3][p[3]].second,l,r));
		++p[x];
		l=r;
	}
	printf("%.20f\n",ans);
	return 0;
}

/*
(gdb) p A[0]
$1 = std::vector of length 2, capacity 2 = {{first = 0, second = 3}, {
    first = 0.5, second = 2}}
(gdb) p A[1]
$2 = std::vector of length 2, capacity 2 = {{first = 0, second = 1}, {
    first = 0.33333333333333331, second = 3}}
(gdb) p A[2]
$3 = std::vector of length 2, capacity 2 = {{first = 0, second = 3}, {
    first = 0.5, second = 2}}
(gdb) p A[3]
$4 = std::vector of length 2, capacity 2 = {{first = 0, second = 4}, {
    first = 1, second = 4}}


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.22222222222222143273

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

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

input:

3
0 -1 0 2
1 1 1 1
-1 1 -1 1

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #3:

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

input:

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1

output:

4.00000000000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

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

input:

1
0 0 0 0

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 7968kb

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

-2921516934.48308181762695312500

result:

wrong answer 1st numbers differ - expected: '3999984000032.0000000', found: '-2921516934.4830818', error = '1.0007304'