QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362475 | #8505. Almost Aligned | ucup-team052# | WA | 1ms | 8040kb | C++23 | 2.7kb | 2024-03-23 15:41:27 | 2024-03-23 15:41:29 |
Judging History
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'