QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211572 | #5479. Traveling Salesperson in an Island | bulijiojiodibuliduo# | RE | 0ms | 4000kb | C++17 | 3.9kb | 2023-10-12 18:42:06 | 2023-10-12 18:42:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
//typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
typedef long long db;
const db EPS = 0;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
bool isSS_strict(P p1, P p2, P q1, P q2){
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) < 0;
}
bool isMiddle(db a, db m, db b) {
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) {
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
bool onSeg(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
bool onSeg_strict(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
const int N=410;
int n,m;
int ok[N][N];
P p2[N];
vector<P> p;
int contain(P q){ //2:inside,1:on_seg,0:outside
int ret = 0;
rep(i,0,n){
P u=p[i],v=p[(i+1)%n];
if(onSeg(u,v,q)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(q.y,u.y) >0 || cmp(q.y,v.y) <= 0) continue;
ret ^= crossOp(q,u,v) > 0;
}
return ret*2;
}
int checkok(int i,int j) {
if (ok[i][j]!=-1) return ok[i][j];
if (i==j) return ok[i][j]=0;
if (j==(i+1)%n) return ok[i][j]=1;
rep(k,0,n) if (isSS_strict(p[i],p[j],p[k],p[(k+1)%n])) {
return ok[i][j]=0;
}
rep(k,0,n) if (onSeg_strict(p[i],p[j],p[k])) {
return ok[i][j]=checkok(i,k)&checkok(k,j);
}
return ok[i][j]=contain((p[i]+p[j])/2)>=1;
}
double dis[410][410];
int main() {
scanf("%d%d",&n,&m);
p.resize(n);
rep(i,0,n) {
scanf("%lld%lld",&p[i].x,&p[i].y);
}
rep(i,0,m) {
scanf("%lld%lld",&p2[i].x,&p2[i].y);
bool sm=0;
rep(j,0,SZ(p)) if (p2[i]==p[j]) sm=1;
if (!sm) {
bool fk=0;
rep(j,0,SZ(p)) if (onSeg_strict(p[j],p[(j+1)%SZ(p)],p2[i])) {
p.insert(p.begin()+j+1,p2[i]);
fk=1;
break;
}
assert(fk);
}
}
//for (auto x:p) printf("-- %lld %lld\n",x.x,x.y);
n=SZ(p);
rep(i,0,n) rep(j,0,n) ok[i][j]=-1;
rep(i,0,n) rep(j,0,n) ok[i][j]=checkok(i,j);
rep(i,0,n) rep(j,0,n) {
assert(ok[i][j]==ok[j][i]);
if (ok[i][j]) {
auto v=(p[i]-p[j]);
dis[i][j]=dis[i][j]=sqrt(v.x*v.x+v.y*v.y);
//printf("%d %d %.10f\n",i,j,dis[i][j]);
} else dis[i][j]=1e10;
}
rep(k,0,n) rep(i,0,n) rep(j,0,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
VI id;
rep(i,0,m) id.pb(find(all(p),p2[i])-p.begin());
sort(all(id));
double ans=0;
rep(i,0,m) ans+=dis[id[i]][id[(i+1)%m]];
printf("%.10f\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3960kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.6568542495
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
16.6491106407
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 2 1 1 2 0 1
output:
5.6568542495
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
16.6491106407
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #5:
score: -100
Runtime Error
input:
76 98 268 97 299 202 133 205 110 251 384 226 332 198 532 241 448 83 268 82 543 62 873 93 387 317 905 90 945 132 827 335 983 222 919 534 945 264 910 287 789 705 837 176 793 563 777 665 782 345 746 315 715 315 810 161 369 599 278 671 641 423 703 344 753 619 672 402 596 709 161 701 216 857 325 942 135 ...