QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95393#5479. Traveling Salesperson in an IslandFHQYWA 2ms3584kbC++205.0kb2023-04-09 15:53:192023-04-09 15:53:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-09 15:53:21]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3584kb
  • [2023-04-09 15:53:19]
  • 提交

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'