#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const double EPS=1e-9;
const double TAU=acos(0)*4;
struct vec{
double x,y;
};
vec add(vec i,vec j){
return {i.x+j.x,i.y+j.y};
}
vec sub(vec i,vec j){
return {i.x-j.x,i.y-j.y};
};
vec mul(double lambda,vec i){
return {i.x*lambda,i.y*lambda};
};
double dist(vec i,vec j){
double dx=i.x-j.x;
double dy=i.y-j.y;
return sqrt(dx*dx+dy*dy);
}
int n;
double k;
int arr[110][4];
vector<vec> p; //stores all points
vector<double> angle;
double diff(double i,double j){
double res=i-j;
while (res<-TAU/2) res+=TAU;
while (res>TAU/2) res-=TAU;
return res;
}
int count(double i){
return floor(i/TAU+0.5);
}
#define id pair<int,double>
#define dii pair<double,ii>
double w[10005][5];
vector<id> al[10005];
priority_queue<dii,vector<dii>,greater<dii> > pq;
bool inter(vec i,vec j,vec a,vec b){
//i.x + j.x*L1 = a.x + b.x*L2
//i.y + j.y*L1 = a.y + b.y*L2
//j.x * L1 - b.x * L2 = a.x - i.x
//j.y * L1 - b.y * L2 = a.y - i.y
//check that L1,L2 in [0,1]
vector<double> v = {
a.x - i.x,
a.y - i.y
};
vector<vector<double> > mat = {
{j.x,-b.x},
{j.y,-b.y}
};
double det=mat[0][0]*mat[1][1]-mat[0][1]*mat[1][0];
if (abs(det)<=1e-9) return false;
vector<vector<double> > imat = {
{mat[1][1],-mat[0][1]},
{-mat[1][0],mat[0][0]}
};
rep(x,0,2) rep(y,0,2) imat[x][y]/=det;
rep(x,0,2){
double res=0;
rep(y,0,2){
res+=imat[x][y]*v[y];
}
if (res<0 || 1<res) return false;
}
return true;
}
bool ok(vec i,vec j){
vector<vec> v={ {-k+2*EPS,-k+EPS},{-k+EPS,k-2*EPS},{k-2*EPS,k-EPS},{k-EPS,-k+2*EPS} };
vector<vec> v2={ {-k+2*EPS,k-EPS},{k-EPS,k-2*EPS},{k-2*EPS,-k+EPS},{-k+EPS,-k+2*EPS} };
rep(x,0,4){
if (inter(i,sub(j,i),v[x],sub(v2[x],v[x]))) return false;
}
return true;
}
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>k;
rep(x,0,n) rep(y,0,4) cin>>arr[x][y];
rep(x,0,4) rep(y,0,4){
if (x==3 || (x && (x+y)%2==0)) arr[n+x][y]=-k;
else arr[n+x][y]=k;
}
n+=4;
//rep(x,0,n){
//rep(y,0,4) cout<<arr[x][y]<<" "; cout<<endl;
//}
rep(x,0,n) p.pub({(double)arr[x][0],(double)arr[x][1]});
rep(x,0,n) p.pub({(double)arr[x][2],(double)arr[x][3]});
rep(x,0,n){
al[x].pub({x+n,0});
al[x+n].pub({x,0});
}
double ans=8*k;
rep(x,0,n) rep(y,x+1,n){
vec temp[4];
vec temp2[4];
double best=1e18;
int idx=-1;
rep(z,0,4){
if (z>=2) swap(x,y);
if (z%2==0) temp2[z]=p[x];
else temp2[z]=p[x+n];
vec base=p[y];
vec dir=sub(p[y+n],p[y]);
double lo=0,hi=1;
rep(x,0,70){
double mi1=lo+(hi-lo)/3,mi2=lo+2*(hi-lo)/3;
if (dist(add(base,mul(mi1,dir)),temp2[z])<dist(add(base,mul(mi2,dir)),temp2[z])){
hi=mi2;
}
else{
lo=mi1;
}
}
temp[z]=add(base,mul(lo,dir));
double curr=dist(temp2[z],temp[z]);
if (curr<best){
best=curr;
idx=z;
}
if (z>=2) swap(x,y);
}
if (ok(temp[idx],temp2[idx])){
//cout<<x<<" "<<y<<" "<<best<<" "<<idx<<endl;
//cout<<temp[idx].x<<" "<<temp[idx].y<<endl;
//cout<<temp2[idx].x<<" "<<temp2[idx].y<<endl;
//rep(z,0,4) cout<<arr[x][z]<<" "; cout<<endl;
//rep(z,0,4) cout<<arr[y][z]<<" "; cout<<endl;
//cout<<endl;
//cout<<"cunny"<<endl;
int IDX1=sz(p),IDX2;
p.pub(temp[idx]);
if (idx==0) IDX2=x;
if (idx==1) IDX2=x+n;
if (idx==2) IDX2=y;
if (idx==3) IDX2=y+n;
//cout<<temp2[idx].x<<" "<<temp2[idx].y<<endl;
//cout<<p[IDX2].x<<" "<<p[IDX2].y<<endl;
al[IDX1].pub({IDX2,best});
al[IDX2].pub({IDX1,best});
if (idx<2) IDX2=y;
else IDX2=x;
al[IDX1].pub({IDX2,0});
al[IDX2].pub({IDX1,0});
}
}
rep(x,0,sz(p)){
angle.pub(atan2(p[x].x,p[x].y)+TAU/2);
//cout<<x<<" "<<p[x].x<<" "<<p[x].y<<" "<<angle[x]<<endl;
}
rep(x,0,n){
rep(y,0,10005) rep(z,0,5) w[y][z]=1e18;
w[x][2]=0;
pq.push({w[x][2],ii(x,2)});
while (!pq.empty()){
double weight;
ii u;
tie(weight,u)=pq.top(),pq.pop();
if (w[u.fi][u.se]!=weight) continue;
double angle1=diff(angle[x],angle[u.fi])+TAU*u.se;
for (auto [it,w2]:al[u.fi]){
int it2=count(angle1+diff(angle[u.fi],angle[it])-diff(angle[x],angle[it]));
if (it2<0 || 4<it2) continue;
if (w[it][it2]>weight+w2){
w[it][it2]=weight+w2;
pq.push({w[it][it2],ii(it,it2)});
}
}
}
//cout<<x<<" "<<w[x][3]<<endl;
ans=min(ans,w[x][3]);
}
cout<<fixed<<setprecision(12)<<ans<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
956 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
960 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
864 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
1 ms |
964 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
16 |
Correct |
1 ms |
964 KB |
Output is correct |
17 |
Correct |
1 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
852 KB |
Output is correct |
19 |
Correct |
1 ms |
852 KB |
Output is correct |
20 |
Correct |
1 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
956 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
960 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
864 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
1 ms |
964 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
16 |
Correct |
1 ms |
964 KB |
Output is correct |
17 |
Correct |
1 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
852 KB |
Output is correct |
19 |
Correct |
1 ms |
852 KB |
Output is correct |
20 |
Correct |
1 ms |
852 KB |
Output is correct |
21 |
Correct |
1 ms |
956 KB |
Output is correct |
22 |
Correct |
2 ms |
852 KB |
Output is correct |
23 |
Correct |
2 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
852 KB |
Output is correct |
25 |
Correct |
2 ms |
852 KB |
Output is correct |
26 |
Correct |
2 ms |
960 KB |
Output is correct |
27 |
Correct |
1 ms |
852 KB |
Output is correct |
28 |
Correct |
2 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
3 ms |
864 KB |
Output is correct |
32 |
Correct |
2 ms |
964 KB |
Output is correct |
33 |
Correct |
2 ms |
960 KB |
Output is correct |
34 |
Correct |
2 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
852 KB |
Output is correct |
36 |
Correct |
2 ms |
860 KB |
Output is correct |
37 |
Correct |
2 ms |
852 KB |
Output is correct |
38 |
Correct |
1 ms |
852 KB |
Output is correct |
39 |
Correct |
2 ms |
852 KB |
Output is correct |
40 |
Correct |
1 ms |
868 KB |
Output is correct |
41 |
Correct |
1 ms |
860 KB |
Output is correct |
42 |
Correct |
1 ms |
852 KB |
Output is correct |
43 |
Correct |
1 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
956 KB |
Output is correct |
3 |
Correct |
1 ms |
852 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
960 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
864 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
1 ms |
964 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
16 |
Correct |
1 ms |
964 KB |
Output is correct |
17 |
Correct |
1 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
852 KB |
Output is correct |
19 |
Correct |
1 ms |
852 KB |
Output is correct |
20 |
Correct |
1 ms |
852 KB |
Output is correct |
21 |
Correct |
1 ms |
956 KB |
Output is correct |
22 |
Correct |
2 ms |
852 KB |
Output is correct |
23 |
Correct |
2 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
852 KB |
Output is correct |
25 |
Correct |
2 ms |
852 KB |
Output is correct |
26 |
Correct |
2 ms |
960 KB |
Output is correct |
27 |
Correct |
1 ms |
852 KB |
Output is correct |
28 |
Correct |
2 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
3 ms |
864 KB |
Output is correct |
32 |
Correct |
2 ms |
964 KB |
Output is correct |
33 |
Correct |
2 ms |
960 KB |
Output is correct |
34 |
Correct |
2 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
852 KB |
Output is correct |
36 |
Correct |
2 ms |
860 KB |
Output is correct |
37 |
Correct |
2 ms |
852 KB |
Output is correct |
38 |
Correct |
1 ms |
852 KB |
Output is correct |
39 |
Correct |
2 ms |
852 KB |
Output is correct |
40 |
Correct |
1 ms |
868 KB |
Output is correct |
41 |
Correct |
1 ms |
860 KB |
Output is correct |
42 |
Correct |
1 ms |
852 KB |
Output is correct |
43 |
Correct |
1 ms |
972 KB |
Output is correct |
44 |
Correct |
925 ms |
2088 KB |
Output is correct |
45 |
Correct |
691 ms |
2048 KB |
Output is correct |
46 |
Correct |
582 ms |
1700 KB |
Output is correct |
47 |
Correct |
404 ms |
1508 KB |
Output is correct |
48 |
Correct |
903 ms |
2096 KB |
Output is correct |
49 |
Correct |
761 ms |
1968 KB |
Output is correct |
50 |
Correct |
572 ms |
1640 KB |
Output is correct |
51 |
Correct |
413 ms |
1416 KB |
Output is correct |
52 |
Correct |
572 ms |
1640 KB |
Output is correct |
53 |
Correct |
546 ms |
1652 KB |
Output is correct |
54 |
Correct |
607 ms |
1708 KB |
Output is correct |
55 |
Correct |
626 ms |
1892 KB |
Output is correct |
56 |
Correct |
650 ms |
1956 KB |
Output is correct |
57 |
Correct |
533 ms |
1584 KB |
Output is correct |
58 |
Correct |
534 ms |
1648 KB |
Output is correct |
59 |
Correct |
551 ms |
1672 KB |
Output is correct |
60 |
Correct |
558 ms |
1676 KB |
Output is correct |
61 |
Correct |
649 ms |
1880 KB |
Output is correct |
62 |
Correct |
3 ms |
960 KB |
Output is correct |
63 |
Correct |
3 ms |
980 KB |
Output is correct |
64 |
Correct |
527 ms |
1824 KB |
Output is correct |
65 |
Correct |
544 ms |
1716 KB |
Output is correct |
66 |
Correct |
369 ms |
1376 KB |
Output is correct |
67 |
Incorrect |
773 ms |
2100 KB |
Output isn't correct |
68 |
Halted |
0 ms |
0 KB |
- |