题解 CF1C 【Ancient Berland Circus】

皎月半洒花

2019-02-12 10:09:34

Solution

其实是一道计算几何。 我们首先考虑,对于给出的三个正多边形顶点,两两连边之后,中垂线交于正多边形所在圆心的中点——显然。那么我们可以凭此求出圆心和半径。 之后对于该多边形,我们考虑,由于其让求的正多边形需要**面积最小**,并且对于给出的三个点,由于在正多边形上的原因,所以都应该是**该正多边形相邻两个顶点在外接圆上所对的圆心角的整数倍** 那么我们就做一个`double`类型的$gcd$就好了——因为在外接圆大小一定时(三点已确定一个圆),对于正$n$边形,其面积与$n$成正相关。所以取$gcd$一定是个最好的选择。 最后的面积嘛…大概只需要余弦定理一下就好。此处借鉴的是第一篇题解里面求面积的方法——提醒一句:第三个角必须yong$2\pi$减去另外两个角得到,如果不这样误差会相当的大……尤其是乘上一堆之后,面积会很不精确$qaq$ $\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}$1 ```cpp #include <cmath> #include <cstdio> #include <iostream> using namespace std ; const double Eps = 1e-4 ; const double Pi = acos(-1.00000) ; struct Node{ bool mark ; // 0 = exist, 1 = inexist ; double x, y ; }A, B, C, O, m1, m2, m3 ; struct Line{ int mark ;//0 : // x-axis, 1: // y-axis, 2: // normal ; double k, b ; double x, y ; // y = kx + b, x = k, y = k ; }L[12] ; double Len[4], agl[4], R, angle ; int i ; double get_x(Line A, Line B){ return A.mark == 0 ? A.x : B.x ; } //which is x = k ; double get_y(Line A, Line B){ return A.mark == 1 ? A.y : B.y ; } //which is y = k ; double dis(Node A, Node B){ return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ; } inline Node get_Mid(Node A, Node B){ return (Node){0, (A.x + B.x) / 2, (A.y + B.y) / 2 } ; } inline Line get_verti(Node n, Line a){ if (!a.mark) return (Line) {1, 0, 0, 0, n.y} ; if (a.mark == 1) return (Line) {0, 0, 0, n.x, 0} ; double kk = -1.0 / a.k, bb = n.y - n.x * kk ; return (Line){2, kk, bb, 0, 0 } ; } inline Line get_Line(Node A, Node B){ if (A. y == B. y) return (Line){1, 0, 0, 0, B.y} ; if (A. x == B. x) return (Line){0, 0, 0, A.x, 0} ; double kk = (A.y - B.y) / (A.x - B.x), bb = A.y - A.x * kk ; return (Line){2, kk, bb, 0, 0} ; } inline Node get_inter(Line A, Line B){ if (A.mark == B.mark && (A.mark == 1 || A.mark == 0) ) return (Node){1, 0, 0 } ; if ((A.mark == 1 && B.mark == 0) || (A.mark == 0 && B.mark == 1)) return (Node){0, get_x(A, B), get_y(A, B)} ; if (A.mark == 1 && B.mark == 2) return (Node){0, (A.y - B.b) / B.k, A.y} ; if (A.mark == 2 && B.mark == 1) return (Node){0, (B.y - A.b) / A.k, B.y} ; if (A.mark == 2 && B.mark == 0) return (Node){0, B.x, B.x * A.k + A.b} ; if (A.mark == 0 && B.mark == 2) return (Node){0, A.x, A.x * B.k + B.b} ; return (Node){0, (A.b - B.b) / (B.k - A.k), (A.b - B.b) / (B.k - A.k) * A.k + A.b} ; } inline double gcd(double a,double b) { if (fabs(b) < Eps) return a ; if (fabs(a) < Eps) return b ; return gcd(b, fmod(a, b)) ; } int main(){ cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y ; A.mark = B.mark = C.mark = 0 ; L[1] = get_Line(A, B), L[2] = get_Line(B, C), L[3] = get_Line(A, C), m1 = get_Mid(A, B), m2 = get_Mid(B, C), m3 = get_Mid(A, C) ; L[4] = get_verti(m1, L[1]), L[5] = get_verti(m2, L[2]), O = get_inter(L[4], L[5]), R = (dis(O, A) + dis(O, B) + dis(O, C)) / 3.0 ; Len[1] = dis(A, B), Len[2] = dis(B, C), Len[3] = dis(A, C) ; for (i = 1 ; i <= 3 ; ++ i) agl[i] = acos(1 - Len[i] * Len[i] / (2 * R * R) ); agl[3] = 2 * Pi - agl[1] - agl[2], angle = gcd(agl[3], gcd(agl[1], agl[2])), printf("%.6lf\n", (Pi * R * R * sin(angle)) / angle) ; return 0 ; } ``` 吐槽: * 我用的是斜截式直线方程……这就需要考虑$k$是否存在,于是我就分了好几种情况ORZ * 这其实是我第一次写计算几何qaq感觉不是很好……一开始没考虑斜率是否是inf……导致一堆nan……qaq