time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output
Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.
In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.
Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.
You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.
Input
The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.
Output
Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.
Examples
input
0.000000 0.000000 1.000000 1.000000 0.000000 1.000000
output
1.00000000
题解:(not me)
The points can be vertices of regular N-polygon, if, and only if, for each pair, difference of their polar angles (as viewed from center of polygon) is a multiple of 2*pi/N. All points should lie on the circle with same center as the polygon. We can locate the center of polygon/circle [but we may avoid this, as a chord (like, say, (x1,y1)-(x2,y2)) is seen at twice greater angle from center, than it is seen from other point of a cricle (x3,y3)]. There are many ways to locate center of circle, the way I used is to build midpoint perpendiculares to segments (x1,y1)-(x2,y2) and (x2,y2)-(x3,y3) in form y = a*x + b and find their intersection. Formula y = a*x + b has drawback that it cannot be used if line is parallel to y, possible workaround is to rotate all points by random angle (using formulae x' = x*cos(a) - y*sin(a), y' = y*cos(a) + x*sin(a) ) until no segments are horizontal (and hence no perperdiculares are vertical).
After the coordinates of the center are known, we use fancy function atan2, which returns angle in right quadrant: a[i] = atan2(y[i]-ycenter, x[i]-xcenter)
Area of regular polygon increases with increasing N, so it is possible just to iterate through all possible values on N in ascending order, and exit from cycle as first satisfying N is found.
Using sin(x) is makes it easy: sin(x) = 0 when x is mutiple of pi. So, for points to belong to regular, N-polygon,
sin( N * (a[i]-a[j]) /2 )=0
because of finite precision arithmetic,
fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps
学好数学,
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
double x[3], y[3], l[3],ang[3],p,s,r,unita ;
const double PI = 3.1415926535;
const double ERR = 0.01;
bool feq (double a, double b) {
return fabs(a-b) < ERR;
}
double fgcd(double a, double b) {
if (feq(a, 0)) return b;
if (feq(b, 0)) return a;
return fgcd(b, fmod(a, b));
}
double dist(double x0, double x1, double y0, double y1) {
return sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));
}
int main() {
for (int i = 0; i < 3; i++)
scanf("%lf %lf", &x[i], &y[i]);
for (int i = 0; i < 3; i++)
l[i] = dist(x[i], x[(i+1)%3], y[i], y[(i+1)%3]);
p = (l[0] + l[1] + l[2]) / 2;
s = sqrt(p * (p-l[0]) * (p-l[1]) * (p-l[2]));
r = l[0] * l[1] * l[2] / (s * 4);
for (int i = 0; i < 3; i++)
ang[i] = acos(1 - l[i]*l[i] / (2 * r * r));
ang[2] = 2 * PI - ang[0] - ang[1];
unita = 0;
for (int i = 0; i < 3; i++)
unita = fgcd(unita, ang[i]);
printf("%.6lf\n", r * r * sin(unita) * PI / unita);
return 0;
}