Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:backup

Posted by yygy at 2023-06-14 20:06:45 on Problem 3521
In Reply To:backup Posted by:yygy at 2023-06-12 23:36:24
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <time.h>
#include <mutex>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef unsigned long long llu;
typedef long long lld;

const int MAXN = 2e5 + 10;
const int INF = 1e9;

int gcd(int a, int b)
{
	if (a == 0)return b;
	if (b == 0)return a;
	if (a % b == 0)return b;
	return gcd(b, a % b);
}

typedef std::pair<int, int> Point;

int last = 0;
std::map<Point, int> id;

struct Segment
{
	Point begin;
	Point end;
};

Segment segments[512];

void ReadPoint(Point& s)
{
	scanf("%d%d", &s.first, &s.second);
}

std::vector<Point> sto;

int QueryId(const Point& s)
{
	const std::map<Point, int>::iterator iter = id.find(s);
	if (iter == id.end())
	{
		sto.push_back(s);
		id[s] = last;
		last++;
		return last - 1;
	}
	else
	{
		return iter->second;
	}
}

Point MakeVector(const Point& a, const Point& b)
{
	return std::make_pair(b.first - a.first, b.second - a.second);
}

int Cross(const Point& ab, const Point& cd)
{
	return ab.first * cd.second - ab.second * cd.first;
}

int Dot(const Point& a, const Point& b)
{
	return a.first * b.first + a.second * b.second;
}

bool OnSegment(const Point& p, const Point& a, const Point& b)
{
	const Point& ap = MakeVector(a, p);
	const Point& ab = MakeVector(a, b);
	if (Cross(ap, ab) == 0)
	{
		const Point& pa = MakeVector(p, a);
		const Point& pb = MakeVector(p, b);
		return Dot(pa, pb) <= 0;
	}

	return false;
}

bool Shared(const Point& a, const int firbidden, const int n)
{
	for (int i = 0; i < n; i++)
	{
		if (firbidden == i)
		{
			continue;
		}

		if (OnSegment(a, segments[i].begin, segments[i].end))
		{
			return true;
		}
	}

	return false;
}

Point origin;

int SqrDis(const Point& a, const Point& b)
{
	int dx = a.first - b.first;
	int dy = a.second - b.second;
	return dx * dx + dy * dy;
}

bool cmp(const Point& a, const Point& b)
{
	return SqrDis(a, origin) < SqrDis(b, origin);
}

double g[512][512];

bool Blocked(const Point& a, const Point& b, const std::vector<Segment>& signs)
{
	for (int i = 0; i < signs.size(); i++)
	{
		const Segment& sign = signs[i];
		const Point& ab = MakeVector(a, b);
		if (OnSegment(sign.begin, a, b))
		{
			const Point& v = MakeVector(sign.begin, sign.end);
			if (Dot(ab, v) >= 0)
			{
				return false;
			}
		}

		if (OnSegment(sign.end, a, b))
		{
			const Point& v = MakeVector(sign.end, sign.begin);
			if (Dot(ab, v) >= 0)
			{
				return false;
			}
		}
	}

	return false;
}

int pre[512];
double dis[512];

double Dij(int s, int t, int n)
{
	for (int i = 0; i < n; i++)
	{
		dis[i] = INF;
	}
	dis[s] = 0;

	bool vis[512] = { false };
	pre[s] = -1;

	for (int i = 0; i < n; i++)
	{
		int minId = -1;
		double minDis = INF;
		for (int j = 0; j < n; j++)
		{
			if (!vis[j] && dis[j] < minDis)
			{
				minId = j;
				minDis = dis[j];
			}
		}

		if (minId == -1)
		{
			return dis[t];
		}

		for (int j = 0; j < n; j++)
		{
			if (dis[minId] + g[minId][j] < dis[j])
			{
				dis[j] = dis[minId] + g[minId][j];
				pre[j] = minId;
			}
		}
	}
	return dis[t];
}

int main(int argc, char* argv[]) {
	int n;
	Point s, t;
	while (cin >> n && n>0)
	{
		sto.clear();
		ReadPoint(s);
		ReadPoint(t);
		id.clear();
		last = 0;
		QueryId(s);
		QueryId(t);

		for (int i = 0; i < n; i++)
		{
			ReadPoint(segments[i].begin);
			ReadPoint(segments[i].end);
		}

		std::vector<Segment> streets;
		std::vector<Segment> signs;

		//找出是stree的部分,两个端点都被共享
		for (int i = 0; i < n; i++)
		{
			if (Shared(segments[i].begin, i, n)
				&& Shared(segments[i].end, i, n))
			{
				streets.push_back(segments[i]);
			}
			else
			{
				signs.push_back(segments[i]);
			}
		}

		for (int i = 0; i < last; i++)
		{
			for (int j = 0; j < last; j++)
			{
				g[i][j] = INF;
			}
		}

		//对每一个street,计算出被分成了几段,对于每一段检测是否可通行
		for (int streetId = 0; streetId < streets.size(); streetId++)
		{
			const Segment& street = streets[streetId];
			std::vector<Point> points;
			points.push_back(street.begin);
			points.push_back(street.end);
			for (int otherId = 0; otherId < streets.size(); otherId++)
			{
				const Segment& other = streets[otherId];
				if (OnSegment(other.begin, street.begin, street.end))
				{
					points.push_back(other.begin);
				}

				if (OnSegment(other.end, street.begin, street.end))
				{
					points.push_back(other.end);
				}
			}

			origin = street.begin;
			//先进行排序
			std::sort(points.begin(), points.end());
			points.erase(std::unique(points.begin(), points.end()), points.end());

			for (int roadId = 0; roadId + 1 < points.size(); roadId++)
			{
				const Point& a = points[roadId];
				const Point& b = points[roadId + 1];
				int idA = QueryId(a);
				int idB = QueryId(b);

				if (!Blocked(a, b, signs))
				{
					g[idA][idB] = sqrt(SqrDis(a, b));
				}

				if (!Blocked(b, a, signs))
				{
					g[idB][idA] = sqrt(SqrDis(b, a));
				}
			}
		}

		//跑一下最短路
		//#TODO
		int sId = QueryId(s);
		int tId = QueryId(t);
		double dis = Dij(sId, tId, last);

		if (dis < INF)
		{
			std::vector<int> trace;
			while (tId != -1)
			{
				trace.push_back(tId);
				tId = pre[tId];
			}

			std::reverse(trace.begin(), trace.end());
			for (int i = 0; i < trace.size(); i++)
			{
				const Point& ps = sto[trace[i]];
				printf("%d %d\n", ps.first, ps.second);
			}

			puts("0");
		}
		else
		{
			puts("-1");
		}
	}

	return 0;
}

/*

*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator