zoj 2102 - Tables

题目：给你一根木棒的两个端点坐标，以及一些高度相同的圆形桌子的圆心和半径，判断木棒状态。

分析：计算几何。如果木棒不掉下来有两种情况：1.重心在桌子上；2.重心两边各有点在桌子上；

            分两种情况计算即可；

           1. 重心在桌子上，只要判断木棒中心O是否在桌子表示的圆内即可；

           2.判断重心两端，将木棒从中间分开，分别判断与圆相交与否即可；

               相交判断，首先判断两点是否都在垂线的同侧：

               在同侧则最近距离在端点；否则为点到直线距离，可以利用|ABxAC/AC|求得。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

typedef struct pnode
{
	double x,y,r;
	pnode(){}
	pnode(double X, double Y, double R = 0) {
		x = X;y = Y;r = R;
	}
}point;
point C[10001];

typedef struct lnode
{
	double x,y,dx,dy;
	lnode(){}
	lnode(double X, double Y, double DX, double DY) {
		x = X;y = Y;dx = DX;dy = DY;
	}
}line;

double dist_p2p(point a, point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double crossproduct(point a, point b, point c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

double dist_p2l(point p, point a, point b)
{
	line l(p.x, p.y, a.y-b.y, b.x-a.x);
	if ((l.dx*(a.y-l.y)-l.dy*(a.x-l.x))*(l.dx*(b.y-l.y)-l.dy*(b.x-l.x)) >= 0)
		return min(dist_p2p(p, a), dist_p2p(p, b));
	return fabs(crossproduct(a, b, p)/dist_p2p(a, b));
}

int main()
{
	point 	A,B,O;
	int 	n,a,b,c;
	while (~scanf("%d",&n) && n) {
		for (int i = 0; i < n; ++ i)
			scanf("%lf%lf%lf",&C[i].x,&C[i].y,&C[i].r);
		scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
		
		point O((A.x+B.x)/2, (A.y+B.y)/2);
		a = b = c = 0;
		for (int i = 0; i < n; ++ i) {
			if (dist_p2p(C[i], O) <= C[i].r)
				c = 1;
			if (dist_p2l(C[i], O, A) <= C[i].r)
				a = 1;
			if (dist_p2l(C[i], O, B) <= C[i].r)
				b = 1;
		}
		
		if (c || a&&b)
			printf("STAY\n");
		else printf("FALL\n");
	}
    return 0;
}

zoj 2102 - Tables

原文：http://blog.csdn.net/mobius_strip/article/details/44708005