解題區►解題區 - UVa

UVa 12779 - The Largest Circle

contents

  1. 1. 題目描述
  2. 2. Solution

題目描述

對於一個平行四邊形，找到平行四邊形內接最大圓面積為何。

並且以分數的方式輸出，保證輸入的四個點一定能構成平行四邊形。

Solution

找到平行四邊形的兩個高中最小得即可。

因此會使用到點線投影方程式，從方程式中可以得知一定能用分數形式輸出，不用特別考慮 -1 的案例輸出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// thanks for flere help debug. 
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
	Pt operator-(const Pt &a) const {
		Pt ret;
		ret.x = x - a.x;
		ret.y = y - a.y;
        return ret;
    }
};
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
	return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
	return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double distProjection(Pt as, Pt at, Pt s) {
	long long a, b, c;
	a = at.y - as.y;
	b = as.x - at.x;
	c = - (a * as.x + b * as.y);
	return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
void distProjection2(Pt as, Pt at, Pt s, long long &p, long long &q) {
	long long a, b, c;
	a = at.y - as.y;
	b = as.x - at.x;
	c = - (a * as.x + b * as.y);
	p = (a * s.x + b * s.y + c) * (a * s.x + b * s.y + c);
	q = a*a + b*b;
}
int main() {
	Pt p[4];
	while(true) {
		int end = 1;
		for(int i = 0; i < 4; i++) {
			scanf("%d %d", &p[i].x, &p[i].y);
			end &= p[i].x == 0 && p[i].y == 0;
		}
		if(end)	
			break;
		double h1 = distProjection(p[0], p[1], p[2]);
		double h2 = distProjection(p[1], p[2], p[3]);
		long long n, m;
		if(h1 <= h2)
			distProjection2(p[0], p[1], p[2], n, m);
		else
			distProjection2(p[1], p[2], p[3], n, m);
		long long g = __gcd(n, m);
		n /= g, m /= g;
		m *= 4;
		g = __gcd(n, m);
		n /= g, m /= g;
		if(min(h1, h2) < eps)
			while(1);
		printf("(%lld/%lld)*pi\n", n, m);
	}
	return 0;
}
/*
0 0 2 3 5 5 3 2
0 0 2 3 6 3 4 0
0 0 10 0 10 10 0 10
0 0 0 0 0 0 0 0
*/