_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

题解 CF1C 【Ancient Berland Circus】

posted on 2019-02-12 10:09:34 | under 题解 |

其实是一道计算几何。

我们首先考虑,对于给出的三个正多边形顶点,两两连边之后,中垂线交于正多边形所在圆心的中点——显然。那么我们可以凭此求出圆心和半径。

之后对于该多边形,我们考虑,由于其让求的正多边形需要面积最小,并且对于给出的三个点,由于在正多边形上的原因,所以都应该是该正多边形相邻两个顶点在外接圆上所对的圆心角的整数倍

那么我们就做一个double类型的 $gcd$ 就好了——因为在外接圆大小一定时(三点已确定一个圆),对于正 $n$ 边形,其面积与 $n$ 成正相关。所以取 $gcd$ 一定是个最好的选择。

最后的面积嘛…大概只需要余弦定理一下就好。此处借鉴的是第一篇题解里面求面积的方法——提醒一句:第三个角必须yong $2\pi$ 减去另外两个角得到,如果不这样误差会相当的大……尤其是乘上一堆之后,面积会很不精确 $qaq$

$\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}$ 1

#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