Computational Geometry

計算幾何

Introduction to Competitive Programming

2024/05/15

浮點數誤差在計算幾何中是非常頭痛的問題，
如果在比賽中沒有遇到，那是代表你有好的計算幾何技巧或者是非常幸運

而如果遇到了則代表你接下來到比賽結束或者 AC 之前，都會非常的痛苦煩躁。

Computational Geometry 計算幾何 Introduction to Competitive Programming 2024/05/15

	double x = 0.1;
	double y = 0.2;
	double z = x+y;
	cout << fixed << setprecision(18) << z << endl;

	void solve(){
	cin >> n;
	int x, y; char ch;
	int sum = 0;
	for(int i = 0; i < n; i++){
	cin >> x >> ch >> y;
	sum += x*100+y;
	}
	cout << sum/100 << "." << setfill('0') << setw(2) << sum%100 << endl;

	#define ld long double
	struct Pt {
	ld x, y;
	Pt(ld _x=0, ld _y=0):x(_x), y(_y) {}

	Pt operator+(const Pt &a){
	return Pt(x+a.x, y+a.y);
	}
	Pt operator-(const Pt &a){
	return Pt(x-a.x, y-a.y);
	}
	Pt operator*(const ld &a){
	return Pt(xa, ya);
	}
	Pt operator/(const ld &a){
	return Pt(x/a, y/a);
	}
	ld operator(const Pt &a){ //計算幾何程式碼中內積通常用表示
	return xa.x + ya.y;
	}
	ld operator^(const Pt &a){ //計算幾何程式碼中外積通常用^表示
	return xa.y - ya.x;
	}
	bool operator<(const Pt &a) const { // 判斷兩點座標先比 x 再比 y
	return x < a.x \|\| (x == a.x && y < a.y);
	}
	};

	Pt arr[N];
	void solve(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> arr[i].x >> arr[i].y;
	for(int i = 0; i < n; i++){
	area += arr[i].x * arr[(i+1)%n].y - arr[(i+1)%n].x*arr[i].y;
	}
	area = abs(area);
	if(area&1) cout << area/2 << ".5" << endl;
	else cout << area/2 << endl;
	}

	bool collinearity(const Pt& a, const Pt& b, const Pt& c){
	return (b-a)^(c-a) == 0;
	}

	bool collinearity(const Pt& a, const Pt& b, const Pt& c){
	return (b-a)^(c-a) < EPS;
	}

	bool inLine(const Pt& p, const Line& li){
	return collinearity(li.st, li.ed, p) && (li.st-p)*(li.ed-p) < 0;
	}

	struct Pt{
	int x,y;
	Pt(){}
	Pt(int _x,int _y){
	x=_x,y=_y;
	}
	Pt operator-(const Pt &a){
	return Pt(x-a.x, y-a.y);
	}
	bool operator<(const Pt &a) const {
	return x < a.x \|\| (x == a.x && y < a.y);
	}
	friend int cross(const Pt& o,const Pt& a,const Pt& b){
	Pt lhs = o-a, rhs = o-b;
	return lhs.xrhs.y - lhs.yrhs.x;
	}
	};
	vector<Pt> convex_hull(vector<Pt> hull){
	sort(hull.begin(),hull.end());
	int top=0;
	vector<Pt> stk;
	for(int i=0;i<hull.size();i++){
	while(top>=2&&cross(stk[top-2],stk[top-1],hull[i])<=0)
	stk.pop_back(),top--;
	stk.push_back(hull[i]);
	top++;
	}
	for(int i=hull.size()-2,t=top+1;i>=0;i--){
	while(top>=t&&cross(stk[top-2],stk[top-1],hull[i])<=0)
	stk.pop_back(),top--;
	stk.push_back(hull[i]);
	top++;
	}
	stk.pop_back();
	return stk;
	}

	double FarthestPair(vector<Pt> arr){
	double ret=0;
	for(int i = 0, j = i+1; i<arr.size(); i++){
	while(distance(arr[i], arr[j]) <= distance(arr[i], arr[(j+1)%arr.size())] ){
	j = (j+1) % arr.size();
	}
	ret = max(ret, distance(arr[i],arr[j]));
	}
	return ret;
	}

	bool cmp(const Pt& lhs, const Pt rhs){
	return atan2(lhs.y, lhs.x) < atan2(rhs.y, rhs.x);
	}

	sort(P.begin(), P.end(), cmp);

	bool cmp(const Pt& lhs, const Pt rhs){
	if((lhs < Pt(0, 0)) ^ (rhs < Pt(0, 0)))
	return (lhs < Pt(0, 0)) < (rhs < Pt(0, 0));
	return (lhs ^ rhs) > 0;
	} // 從 270 度開始逆時針排序

	sort(P.begin(), P.end(), cmp);

	#define EPS 1e-8

	Pt P0, P1, A;

	double check(double t){ // 回傳點 A, B 的距離
	double B = P0 * t + P1 * (1.0-t);
	return dis(A, B);
	}

	double PointAndSegmentDistance(){
	double l = 0.0, r = 1.0;
	while(r - l > EPS){
	double ml = (l+l+r)/3.0, mr = (l+r+r)/3.0;
	if(check(ml) < check(mr)) r = mr;
	else l = ml;
	}
	return check(l);
	}

	Pt arr[MXN];
	double checky(double x, double y) {
	double cmax = 0;
	for(int i = 0; i < n; i++) {
	cmax = max(cmax,(arr[i].x - x) * (arr[i].x - x) +
	(arr[i].y - y) * (arr[i].y - y));
	}// 過程中回傳距離^2 避免不必要的根號運算
	return cmax;
	}
	double checkx(double x){
	double yl = -1e9, yr = 1e9;
	while(yr - yl > EPS) {
	double ml = (yl+yl+yr) / 3, mr = (yl+yr+yr) / 3;
	if (checky(x, ml) < checky(x, mr)) yr = mr;
	else yl = ml;
	}
	}
	double xl = -1e9, xr = 1e9;
	while(xr - xl > EPS) {
	double ml = (xl+xl+xr) / 3, mr = (xl+xr+xr) / 3;
	if (checkx(ml) < checkx(mr)) xr = mr;
	else xl = ml;
	}