HDU 5563 Clarke and five-pointed star

Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke turned into a learner of geometric.

When he did a research with polygons, he found he has to judge if the polygon is a five-pointed star at many times. There are 5 points on a plane, he wants to know if a five-pointed star existed with 5 points given.

Input

The first line contains an integer , the number of the test cases.

For each test case, 5 lines follow. Each line contains 2 real numbers , denoting the coordinate of this point.

Output

Two numbers are equal if and only if the difference between them is less than .

For each test case, print  if they can compose a five-pointed star. Otherwise, print . (If 5 points are the same, print . )

Sample Input

2
3.0000000 0.0000000
0.9270509 2.8531695
0.9270509 -2.8531695
-2.4270509 1.7633557
-2.4270509 -1.7633557
3.0000000 1.0000000
0.9270509 2.8531695
0.9270509 -2.8531695
-2.4270509 1.7633557
-2.4270509 -1.7633557      

Sample Output

Yes

No

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100005;
const int base = 1e9 + 7;
const double eps = 1e-4;
int T, cnt;
double x[5], y[5], dis[5];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        for (int i = 0; i < 5; i++) scanf("%lf%lf", &x[i], &y[i]);
        int flag = 0;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
                dis[j] = (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);
            sort(dis, dis + 5);
            if (dis[2] - dis[1] < eps&&dis[4] - dis[3] < eps)
            if (dis[3] / dis[2]>1.3 || dis[3] < eps) flag++;
        }
        if (flag == 5) printf("Yes\n"); else printf("No\n");
    }
    return 0;
}