QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95393 | #5479. Traveling Salesperson in an Island | FHQY | WA | 2ms | 3584kb | C++20 | 5.0kb | 2023-04-09 15:53:19 | 2023-04-09 15:53:21 |
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 bool onsegment (Point s,Point t,Point a) {
return sgn((t-s)^(a-s))==0 && sgn((t-s)^(a-s))>0 && sgn((s-t)^(a-t))>0;
}
inline int Inter (Point a) {
int cnt=0;
for (int i=1;i<=n;++i) {
int u=i;
int v=i%n+1;
if ((onsegment (P[u],P[v],a)) || P[u]==a) return 1; //在多边形上
double k = (P[v]-P[u])^(a-P[u]);
if (k>0 && P[u].y<a.y && a.y<=P[v].y) cnt^=1;
if (k<0 && P[u].y>=a.y && a.y>P[v].y) cnt^=1;
}
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[v]-P[u]);
double c2 = (_Node[b]-P[u]) ^ (P[v]-P[u]);
double c3 = (P[u]-_Node[a]) ^ (_Node[b]-_Node[a]);
double c4 = (P[v]-_Node[a]) ^ (_Node[b]-_Node[a]);
if ((sgn(c1)*sgn(c2)<0) && (sgn(c3)*sgn(c4)<0)) return false;
if (onsegment (_Node[a],_Node[b],P[i])) return false;
}
Point _mid = _Node[a] + _Node[b];
_mid.x/=2.0;
_mid.y/=2.0;
if (Inter (_mid)) return true;
else return false;
}
double dis[N][N];
Point Origin;
int Now_id;
inline bool cmp (int a,int b) {
return dis[a][Now_id]<dis[b][Now_id];
}
vector<int> dot[N];
vector<int> _P;
void solve() {
cin >> n >> m;
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 (onsegment (P[u],P[v],Node[i]) || Node[i]==P[u]) {
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: 0
Wrong Answer
time: 2ms
memory: 3584kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
0.000000000000000
result:
wrong answer 1st numbers differ - expected: '5.6568542', found: '0.0000000', error = '1.0000000'