#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+EPS,-k},{-k,k-EPS},{k-EPS,k},{k,-k+EPS} };
vector<vec> v2={ {-k+EPS,k},{k,k-EPS},{k-EPS,-k},{-k,-k+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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
956 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
956 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
1 ms |
956 KB |
Output is correct |
| 4 |
Correct |
1 ms |
852 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
