#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);
}

int QueryId(const Point& s)
{
	const std::map<Point, int>::iterator iter = id.find(s);
	if (iter == id.end())
	{
		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;
		}
	}
}

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 main(int argc, char *argv[]) {
	int n;
	Point s, t;
	while (cin >> n)
	{
		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
		}
	}

	return 0;
}

/*

*/

• Re:backup (5793) yygy 2023-06-14 20:06:45