ZOJ Problem Set - 2102 Tables
Granny likes dropping around in the neighborhood. She is rather aged so she always carries a stick to assist walking. When she comes to a house, she wants to put her stick somewhere, actually anywhere but on the ground, otherwise she has to bend over to pick it up and what a misery it is for her! So she finds some round tables. Err�� so far so good, except the fact that, you know, she is not a physicist. She takes out a PDA and calculates whether the stick will fall to the ground. And she is so proud that the software is written by you, her favorite grandchild.
Input
Input contains multiple test cases. Each case begins with an integer N (0 < N <= 10000) - the number of round tables. N lines follow, each of which contains three integers, xi, yi and ri - the center and radius of the ith round table. Tables do not overlap with each other. The last line contains four integers x1, y1, x2 and y2, where (x1, y1) and (x2, y2) is the two end points of the stick. You may assume the stick is thin and its mass is equally distributed.
A test case with a single 0 signals the end of input, and this test case is not to be processed.
Output
One line for each test case, which contains a single word "STAY" or "FALL". Granny is a reasonable person and she will not bother the program about cases that it might or might not fall. But unfortunately, as mentioned earlier, she is unable to instruct you about physics.
Sample Input
1
0 0 2
0 0 1 1
1
0 0 2
0 0 9 9
2
0 0 2
9 9 2
0 0 9 9
0
Sample Output
STAY
FALL
STAY
Author: WU, Jiazhi
Source: Zhejiang University Local Contest 2004
#include <bits/stdc++.h>
using namespace std;
struct node{
double x,y,r;
}th[10010];
double dis(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2)*(x1-x2)*1.0 + (y1-y2)*(y1-y2)*1.0);
}
bool fou(double x1,double y1,double x2,double y2){
if(x1*x2 + y1*y2 >= 0) return true;
else return false;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF && n){
for(int i = 0; i < n; i ++){
scanf("%lf %lf %lf", &th[i].x, &th[i].y, &th[i].r);
}
double x1,x2,y1,y2;
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
bool zx = false, l = false, r = false;
double xz = (x1 + x2) / 2.0, yz = (y1 + y2) / 2.0;
int i;
for(i = 0; i < n; i ++){
if(dis(xz, yz, th[i].x, th[i].y) <= th[i].r){
zx = true;
}else {
double xline, yline, xline2, yline2;
double xpoint, ypoint, xpoint2, ypoint2;
xline = x1-xz;
yline = y1-yz;
xpoint = x1-th[i].x;
ypoint = y1-th[i].y;
xline2 = x2-xz;
yline2 = y2-yz;
xpoint2 = x2-th[i].x;
ypoint2 = y2-th[i].y;
if(fou(xline, yline, xpoint, ypoint) && fou(xz-x1, yz-y1, xz-th[i].x, yz-th[i].y)){
double ju = fabs(xline*ypoint - yline*xpoint) / dis(x1, y1, xz,yz);
if(ju <= th[i].r){
if(x1 == min(x1, x2)) l = true;
else r = true;
}
}else {
double ju = min(dis(xz, yz, th[i].x, th[i].y), dis(x1,y1, th[i].x, th[i].y));
if(ju <= th[i].r) {
if(x1 == min(x1, x2)) l = true;
else r = true;
}
}
if(fou(xline2, yline2, xpoint2, ypoint2) && fou(xz-x2,yz-y2,xz-th[i].x,yz-th[i].y)){
double ju = fabs(xline2*ypoint2 - yline2*xpoint2) / dis(x2, y2, xz,yz);
if(ju <= th[i].r){
if(x2 == min(x1, x2)) l = true;
else r = true;
}
}else {
double ju = min(dis(xz, yz, th[i].x, th[i].y), dis(x2,y2, th[i].x, th[i].y));
if(ju <= th[i].r) {
if(x2 == min(x1, x2)) l = true;
else r = true;
}
}
}
if(zx || (l && r)) break;
}
if(i == n) cout << "FALL" << endl;
else cout << "STAY" <<endl;
}
return 0;
}