求交点的代码似乎是有问题,但是我真找不出来哪里有问题
查看原帖
求交点的代码似乎是有问题,但是我真找不出来哪里有问题
819682
Exile_Code楼主2024/1/26 18:59
#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>
#define ull             unsigned long long 
#define ll              long long
#define pll             pair<ll ,ll>
#define ft              first
#define sd              second
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,n)       for(ll (i)=0;(i)<(n);(i)++)   
#define forne(i,n)      for(ll (i)=1;(i)<=(n);(i)++)
#define rforn(i,n)      for(ll (i)=(n-1);i>=0;i--)
#define rforne(i,n)     for(ll (i)=n;i>=1;i--)
#define vv              vector
#define inf32           INT32_MAX
#define inf64           INT64_MAX
#define LD              double
#define PI              acos(-1)
#define debug(a,b)		cout<<a<<b
const int N = 4e5 + 100;
const int mod = 998244353;
ll T;

//点类
struct Point {
	LD x, y;
	Point(LD x, LD y) { this->x = x;	this->y = y; }
	Point() {}
#define line Point 
	//点的加减乘运算
	Point operator+(Point b) { return Point(this->x + b.x, this->y + b.y); }
	Point operator-(Point b) { return Point(this->x - b.x, this->y - b.y); }
	Point operator*(LD t) { return Point(this->x * t, this->y * t); }
	LD operator*(Point b) { return this->x * b.x + this->y * b.y; }
	bool operator==(Point b) { return this->x == b.x && this->y == b.y; }
};
class Geomtry_tool {
public:
	//求长度
	static LD len(line a) { return sqrt(a.x * a.x + a.y * a.y); }
	//求两点距离
	LD dis(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
	//两个向量求角度,使用的是余弦定理求arccos
	static LD angle(line a, line b) { return acos(a * b / len(a) / len(b)); }
	//两个向量求叉积
	static LD cross(line a, line b) { return a.x * b.y - a.y * b.x; }
	//epslion,判断是否等于0
	static int sgn(LD x) { LD eps = 1e-8; return abs(x) <= eps ? 0 : x > 0 ? 1 : -1; }
	//防止负0的发生
	static void zero(Point& a) { LD eps = 1e-8; if (abs(a.x) <= eps)a.x = 0; if (abs(a.y) <= eps)a.y = 0; }
	//可以用来判断c在b的左侧还是右侧
	//大于0,c在ab左侧;小于0,c在ab右侧;等于0,三点共线
	static LD cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
	//三点点积ab*ac
	static LD dot(Point a, Point b, Point c) { return (b - a) * (c - a); }
	//判断直线与线段的交点情况,在同侧则无交点;
	//如果是判断线段与线段有无交点,则需要分别设ab,cd为直线,进行两次判断
	static bool l_S_inter(Point a, Point b, Point c, Point d) {
		return sgn(cross(a, b, c) * cross(a, b, d)) <= 0;//直线与线段
	}
	//线段与线段
	static bool S_S_inter(Point a, Point b, Point c, Point d) {
		return l_S_inter(a, b, c, d) && l_S_inter(c, d, a, b);
	}
	//求两直线的交点
	static Point getNode(Point a, line u, Point b, line v) {
		LD t = cross((a - b), v) / cross(v, u);//求面积之比
		return a + u * t;
	}
	static Point rotate(Point a, LD b) { //将某点绕原点逆时针旋转b角度
		return { a.x * cos(b) - a.y * sin(b), a.x * sin(b) + a.y * cos(b) };
	}
	static LD get_S(vv<Point>p) {//求某个多边形点集的面积
		LD res = 0;
		for (int i = 2; i < p.size(); i++) {
			res += cross(p[i] - p[1], p[i+1] - p[1]);
		}
		return res / 2;
	}
};
struct Line { Point s, e; };
//半平面交
class Half_plane {
private:
	Geomtry_tool fn;
public:
	int h = 1, t = 1;
	static LD angle(Line a) {//求极角
		return atan2(a.e.y - a.s.y, a.e.x - a.s.x);
	}
	struct cmp {
		bool operator()(Line a, Line b) {//极角+左侧优先排序
			LD A = angle(a), B = angle(b); LD eps = 1e-12;
			return fabs(A - B) > eps ? A < B : (a.e - a.s)* (b.e - a.s) < 0;
		}
	};
	Point cross(Line a, Line b) {//求ab两线交点
		return fn.getNode(a.s, a.e - a.s, b.s, b.e - b.s);
	}
	bool right_nd(Line a, Line b, Line c) {//判断bc交点是否在a右侧
		Point p = cross(b, c);
		return fn.sgn((a.e - a.s) * (p - a.s)) < 0;
	}
	LD half_plane(vv<Line>& a, vv<Line>q) {
		q = vv<Line>(a.size() + 2);
		sort(a.begin() + 1, a.end(), cmp());
		int h = 1, t = 1; q[1] = a[1];
		int n = a.size() - 1;
		cout << "..............." << endl;
		for (int i = 2; i <= n; i++) {
			//必须先弹出尾再弹出头
			if (fn.sgn(angle(a[i]) - angle(a[i - 1])) == 0)continue;
			while (h < t && right_nd(a[i], q[t], q[t - 1]))
				t--;
			while (h < t && right_nd(a[i], q[h], q[h + 1]))
				h++;
			q[++t] = a[i];
		}
		while (h < t && right_nd(q[h], q[t], q[t - 1]))t--;
		q[++t] = q[h];
		int k = 0;
		vv<Point>p(t - h);
		for (int i = h; i < t-1; i++)
			p[++k] = cross(q[i], q[i + 1]);
		return fn.get_S(p);
	}
};
Geomtry_tool fn;
void solve() {
	int n; cin >> n;
	vv<Line>nums(530);
	int cnt = 0;
	forn(i, n) {
		int m; cin >> m;
		vv<Point>p(m);
		forn(i, m) {
			cin >> p[i].x >> p[i].y;
		}
		forn(i, m) {
			nums[++cnt] = { p[i],p[(i + 1) % m] };
		}
	}
	nums.resize(cnt + 1);
	Half_plane hp;
	vv<Line>rs;
	printf("%.3lf", hp.half_plane(nums,rs));
}
int main() {

	//std::ios::sync_with_stdio(false);
	T = 1;
	//cin >> T;

	while (T--)
		solve();

}
2024/1/26 18:59
加载中...