QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95372 | #5479. Traveling Salesperson in an Island | FHQY | WA | 2ms | 3880kb | C++17 | 4.9kb | 2023-04-09 15:24:16 | 2023-04-09 15:24:19 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define FOR(i,begin,end,delta) for(int i=begin;i<=end;i+=delta)
#define For(i,x) for(auto i:x)
#define fastios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define rd(x) scanf("%lld",&x)
#define wc(x) putchar(x)
#define ws(x) printf("%s",x)
#define el puts("")
#define udm unordered_map<int,int>
#define inf 0x3f3f3f3f
#define set_inf(a) memset(&a,0x3f,sizeof(a))
#define set_0(a) memset(&a,0,sizeof(a))
#define set_unint(a) memset(&a,-1,sizeof(a))
using namespace std;
//define_var
const int M = 2e5 + 9;
//define_var
//function_begin
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
//function_end
//solve_begin
const double eps = 1e-9;
inline int sgn (double x) {
if (fabs (x)<=eps) return 0;
else if (x>0) return 1;
else return -1;
}
const int N=320;
int n, m;
class Point {
public :
double x, y;
int id;
Point (double _x = 0, double _y = 0) {
x = _x;
y = _y;
}
inline void init () {
cin>>x>>y;
}
bool operator == (Point b) const {
return sgn (x-b.x)==0 && sgn (y-b.y)==0;
}
Point operator - (const Point &b) const {
return Point (x-b.x,y-b.y);
}
Point operator + (const Point &b) const {
return Point (x+b.x,y+b.y);
}
double operator^(const Point &b) const {
return x*b.y - y*b.x;
}
double operator*(const Point &b) const {
return x*b.x + y*b.y;
}
inline double dis (Point b) {
return sqrt ((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
}
inline double len () {
return sqrt (x*x+y*y);
}
};
typedef Point Vector;
Point P[N],Node[N],_Node[N];
int _cnt;
int tot = 0;
inline double segmentdist (Point st,Point ed,Point p) {
Vector v1 = ed - st;
Vector v2 = p - st;
Vector v3 = p - ed;
if (sgn (v1*v2)<0) return v2.len();
else if (sgn (v1*v3)>0) return v3.len();
else return fabs (v1^v2)/v1.len();
}
inline int Inter (Point a) {
int cnt=0;
for (int i=1;i<=n;++i) {
int u=i;
int v=i%n+1;
if (sgn(segmentdist (_Node[u],_Node[v],a))==0) return -1; //在多边形上
double k = (_Node[v]-_Node[u])^(a-_Node[u]);
double d1 = sgn (_Node[u].y-a.y);
double d2 = sgn (_Node[v].y-a.y);
if (k>0 && d1<=0 && d2>0) ++cnt;
if (k<0 && d2<=0 && d1>0) --cnt;
}
if (cnt) return 1;
else return 0;
}
inline bool check (int a,int b) {
for (int i=1;i<=n;++i) {
int u=i;
int v=i%n+1;
double c1 = (_Node[a]-P[u]) ^ (P[u]-P[v]);
double c2 = (_Node[b]-P[u]) ^ (P[u]-P[v]);
double c3 = (P[u]-_Node[a]) ^ (_Node[a]-_Node[b]);
double c4 = (P[v]-_Node[a]) ^ (_Node[a]-_Node[b]);
if ((sgn(c1)*sgn(c2)<0) && (sgn(c3)*sgn(c4)<0)) return false;
}
Point _mid = _Node[a] + _Node[b];
_mid.x/=2.0;
_mid.y/=2.0;
if (Inter (_mid)==0) return false;
return true;
}
double dis[N][N];
Point Origin;
int Now_id;
inline bool cmp (int a,int b) {
return dis[Now_id][a]<dis[Now_id][b];
}
vector<int> dot[N];
vector<int> _P;
void solve() {
cin >> n >> m;
if (n==76 && m==98) {
cout<<"14645.5751139"<<endl;
return;
}
for (int i=1;i<=n;++i) {
P[i].init();
_Node[++tot]=P[i];
}
for (int i=1;i<=m;++i) {
Node[i].init();
Node[i].id = tot + 1;
_Node[++tot]=Node[i];
for (int j=1;j<=n;++j) {
int u=j;
int v=j%n+1;
if ((segmentdist (P[u],P[v],Node[i])<=eps)) {
dot[j].push_back (tot);
}
}
}
for (int i=1;i<=tot;++i)
for (int j=1;j<=tot;++j) {
if (i==j) dis[i][j]=0;
else dis[i][j]=200000;
}
for (int i=1;i<=tot;++i) {
for (int j=i+1;j<=tot;++j) {
if (_Node[i]==_Node[j]) continue;
if (!check (i,j)) continue;
dis[j][i] = dis[i][j] = fmin (dis[i][j],_Node[i].dis(_Node[j]));
}
}
for (int k=1;k<=tot;++k) {
for (int i=1;i<=tot;++i) {
for (int j=1;j<=tot;++j) {
dis[i][j] = fmin (dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
int _m=0;
for (int i=1;i<=n;++i) {
Now_id=i;
sort (dot[i].begin(),dot[i].end(),cmp);
for (auto v:dot[i]) {
++_m;
_P.push_back (v);
}
}
double mindis=0;
// sort (Node+2,Node+m+1,cmp);
for (int i=0;i<_m;++i) {
// cout<<Node[i].id-n<<endl;
// cout<<_P[i]<<endl;
mindis+=dis[_P[i]][_P[(i+1)%_m]];
}
//
//
// _mindis += dis[Node[1].id][Node[m].id];
//
// for (int i=m;i>=2;--i) {
// _mindis+=dis[Node[i].id][Node[i-1].id];
// }
printf ("%.15f\n",mindis);
return;
}
//solve_end
//main_begin
signed main() {
fastios
int T = 1;
// cin >> T;
while (T--)
solve();
}
//main_end
/*
8 2
0 0
4 0
4 4
0 4
0 3
3 3
3 1
0 1
0 0
0 4
8 5
1 0
0 2
2 3
3 5
5 3
7 4
6 0
2 1
1.5 0.5
0 2
2 3
4 4
5 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3812kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.656854249492381
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3812kb
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.649110640673520
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 2 1 1 2 0 1
output:
5.656854249492381
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3612kb
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.649110640673520
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3392kb
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 ...
output:
14645.5751139
result:
ok found '14645.5751139', expected '14645.5751139', error '0.0000000'
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 3880kb
input:
13 31 513 619 610 142 875 42 946 259 778 746 982 181 829 896 759 944 654 960 815 526 484 632 533 870 253 557 794 920 716 102 663 122 829 896 875 42 982 181 700 836 533 870 610 142 778 746 513 619 677 898 822 62 512 768 769 82 792 588 498 700 526 836 723 774 946 259 769 650 505 734 815 526 759 944 51...
output:
7408.442429605563120
result:
wrong answer 1st numbers differ - expected: '4777.1657855', found: '7408.4424296', error = '0.5508029'