2013
11-10

# Happy Birthday!

There are three berries on a round birthday cake. You are required to divide the cake into three identical parts such that each part contains exactly one berry. To make it easy, it is assumed that the radius of the berries is 0 and each part of the cake is a sector with 120 degrees. Any line that divides the cake should not go through any berry.

The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each case contains exactly 7 integers r, x1, y1, x2, y2, x3 and y3. r is the radius of the cake, (xi, yi) is the coordinates of i-th berry. The center of the cake is at (0, 0) and it's confirmed that all the berries will be on the cake.

For each case, output ‘Yes’ if there is a valid solution, ‘No’ otherwise.

2
2 1 1 -1 1 0 -1
10 0 9 1 8 -1 8


Yes
No


/* @author:张龙acmilan_fan@yahoo.cn */
import java.io.*;
public class Main {
static double A = Math.PI*2/3;
public static void main(String[] args)throws Exception{

String s = br.readLine();
String[] ss;
int num = Integer.parseInt(s);
int x1, y1, x2, y2, x3, y3;
for(int i=0;i< num;i++){
ss = s.split(" ",7);
x1 = Integer.parseInt(ss[1]);
y1 = Integer.parseInt(ss[2]);
x2 = Integer.parseInt(ss[3]);
y2 = Integer.parseInt(ss[4]);
x3 = Integer.parseInt(ss[5]);
y3 = Integer.parseInt(ss[6]);
System.out.println(checkPos(x1, y1, x2, y2, x3, y3)?"Yes":"No");
}
}

static boolean checkPos(int x1, int y1, int x2, int y2, int x3, int y3){
//if one is in the center, this is impossible
if(x1==0 && y1==0 || x2==0 && y2==0 || x3==0 && y3==0)
return false;
double angle = Math.atan2(x1, y1);
double angle2 = Math.atan2(x2, y2);
double angle3 = Math.atan2(x3, y3);
//if two points are of the same angle
if(angle==angle2 || angle2==angle3 || angle3==angle)
return false;
double d12 = get(angle, angle2);
double d23 = get(angle2, angle3);
double d31 = get(angle3, angle);
//120 degrees each
if(d12==d23 && d23==d31 && d31==d12)
return true;
//maximum distinction is less than 120 degrees
if(checkVal(d12) && checkVal(d23) && checkVal(d31))
return false;
return true;
}
static double get(double a, double a2){
double dis = Math.abs(a-a2);
return dis>Math.PI ? 2*Math.PI-dis:dis;
}
static boolean checkVal(double d){
return d<=A;
}
}

1. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。