求助,方法用的董晓的,但不知道哪里错了
查看原帖
求助,方法用的董晓的,但不知道哪里错了
819682
Exile_Code楼主2024/1/26 09:42
#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); }
	//求两点距离
	ll 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) };
	}
};

//凸包
class Andrew {
	Geomtry_tool fn;
public:
	int top = 0;
	struct cmp {
		bool operator()(const Point& a, const Point& b) {
			return a.x == b.x ? a.y < b.y : a.x < b.x;
		}
	};
	LD Andrew_lenth(vv<Point>& p, vv<Point>& s) {
		int n = p.size()-1;
		sort(p.begin() + 1, p.end(), cmp());
		s.resize(p.size() + 2);
		//最左下和最右上的两个点一定是在凸包上的
		forne(i, n) {//下凸包
			while (top > 1 && fn.sgn(fn.cross(s[top - 1], s[top], p[i]) <= 0))
				top--;
			s[++top] = p[i];
		}
		int t = top;
		for (int i = n - 1; i >= 1; i--) {//上凸包
			while (top > t && fn.sgn(fn.cross(s[top - 1], s[top], p[i])) <= 0)
				top--;
			s[++top] = p[i];
		}
		LD res = 0;
		for (int i = 1; i < top; i++)
			res += fn.dis(s[i], s[i + 1]);
		return res;
	}
	//旋转卡壳,用叉积可以找离一条线垂直最高或最低,用点积可以找离一条线水平最左或最右的点(点积的几何意义是b在a的投影长度)
	LD rotating_calipers(vv<Point>& s) {
		int n = top - 1;
		ll res = 0;
		for (int i = 1, j = 2; i <= n; i++) {
			while (fn.cross(s[i], s[i + 1], s[j])
				< fn.cross(s[i], s[i + 1], s[j + 1]))
				j = j % n + 1;
			res = max(res, max(fn.dis(s[i], s[j])
				, fn.dis(s[i + 1], s[j])));
		}
		return res;
	}
};
Geomtry_tool fn;

void solve() {

	int n; cin >> n;
	
	double ans = 1e20;
	int a, b, c;
	a = 2, b = 2;
	vv<Point>rs(n + 1);
	vv<Point>p(4);
	forne(i, n)
		cin >> rs[i].x>>rs[i].y;
	Andrew aw;
	vv<Point>nums;
	aw.Andrew_lenth(rs,nums);
	n = aw.top - 1;
	for (int i = 1; i <= n; i++) {
		while (fn.cross(nums[i], nums[i + 1], nums[a])
			< fn.cross(nums[i], nums[i + 1], nums[a + 1]))
			a = a % n + 1;
		while (fn.dot(nums[i], nums[i + 1], nums[b])
			< fn.dot(nums[i], nums[i + 1], nums[b + 1]))
			b = b % n + 1;
		if (i == 1)
			c = a;
		while (fn.dot(nums[i + 1], nums[i], nums[c])
			< fn.dot(nums[i + 1], nums[i], nums[c + 1]))
			c = c % n + 1;
		double d = fn.dis(nums[i], nums[i + 1]);
		double H = fn.cross(nums[i], nums[i + 1], nums[a]) / d;
		double R = fn.dot(nums[i], nums[i + 1], nums[b]) / d;
		double L = fn.dot(nums[i + 1], nums[i], nums[c]) / d;

		debug(d, ' ');
		debug(H, ' ');
		debug(R, ' ');
		debug(L, '\n');

		if (ans > (R + L - d) * H) {
			ans = (R + L - d) * H;
			p[0] = nums[i + 1] + (nums[i] - nums[i + 1]) * (L / d);
			p[1] = nums[i] + (nums[i + 1] - nums[i]) * (R / d);
			p[2] = p[1] + fn.rotate(Point(nums[i + 1]-nums[i]), PI / 2.0) * (H / d);
			p[3] = p[0] + fn.rotate(Point(nums[i + 1]-nums[i]), PI / 2.0) * (H / d);
		}
	}
	printf("%.5lf\n", ans);
	
	int k = 0;
	forn(i, 4)
		if (p[i].y < p[k].y)
			k = i;
	for (int i = 1; i <= 4; i++) {
		fn.zero(p[k]);
		printf("%.5lf %.5lf\n", p[k].x, p[k].y);
		k = k % 4 + 1;
	}

}
int main() {

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

	while (T--)
		solve();

}
2024/1/26 09:42
加载中...