題目：?http://codeforces.com/contest/1/problem/C

?

題意：給你一個正凸多邊形的三個點，然后求出這個正凸多邊形的面積的最小值。

方法是這樣的：以這三個點做一個三角形，求出這個三角形的外心（外接圓的圓心），這個點也就是外接多邊形的中心

然后找出內角所對應的邊數的GCD

當然，內角所對應的邊數不一定是整數，我們需要用double的GCD和LCM進行計算，求出最小邊數。

#include <stdio.h> #include <math.h> const double eps=1e-4; const double PI=acos(-1.0);double gcd(double x,double y) {return y>eps? gcd(y,x-floor(x/y)*y):x; }double bcos(double a,double b,double c) {return acos((a*a+b*b-c*c)/(2*a*b)); } int main() {double ax,ay,bx,by,cx,cy;scanf("%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy);double a=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));double b=sqrt((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy));double c=sqrt((bx-cx)*(bx-cx)+(by-cy)*(by-cy));double p=(a+b+c)/2;double s=sqrt(p*(p-a)*(p-b)*(p-c));double R=(a*b*c)/(4*s);double A=bcos(b,c,a);double B=bcos(a,c,b);double C=bcos(a,b,c);double n=PI/gcd(A,gcd(B,C));printf("%.11lf\n",R*R*sin(2*PI/n)*n/2);return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Beta Round #1--C题（多边形求最小面积）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。