HDU 4637 Rain on your Fat brother 线段与半圆和线段交 简单题
题意：
应该不难读懂。
做法：
我们可以把雨滴看做静止不动，然后maze（这题的那个人）就是往左上方运动就可以了，计算出maze能跑到的最远的点，然后就是求起点和终点所构成的线段与每个雨滴交的时间，注意题目说每个雨滴可能会相交，所以我们对于每个雨滴算出相交的区间，然后对这些区间进行合并并且计算答案。
注意点：
1.maze有可能一开始就在雨滴里面。
2.还有maze穿了一部分的雨滴就被追上了。 （竟然没有这种数据）
3.两线段共线的情况，就是三角形右边的那条边 与 maze的线段共线， 这种情况之下也要细分，但我没判这种情况也AC了，说明没有这种数据，但考虑问题时我们需要把它考虑进去。 （竟然没有这种数据）
知道以上注意点AC应该不远了，毕竟不是什么难题，我的代码没有写第三种情况。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define pii pair <double, double>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
const double eps = 1e-8;
int dcmp(double x) {
if (fabs(x) < eps)
return 0;
return x > eps ? 1 : -1;
}
struct point {
double x, y;
point() {
}
point(double x, double y) :
x(x), y(y) {
}
double operator *(const point &t) const {
return x * t.x + y * t.y;
}
point operator -(const point &t) const {
return point(x - t.x, y - t.y);
}
point operator +(const point &t) const {
return point(x + t.x, y + t.y);
}
point operator *(const double &t) const { // 注意是 点乘
return point(t * x, t * y);
}
} s, e;
double v1, v2, v, t, x, T;
double ans;
int n;
inline double F(double x) {
return x * x;
}
double cross(const point &o, const point &a, const point &b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
double dis(const point &a, const point &b) {
return sqrt(F(a.x - b.x) + F(a.y - b.y));
}
bool segSegIntersect(const point &a, const point &b, const point &l, const point &r) { //两线段相交(不考虑共线)
return cross(a, b, l) * cross(a, b, r) < eps
&& cross(l, r, a) * cross(l, r, b) < eps;
}
double intersect(const point &a, const point &b, const point &l, const point &r) { // 两直线求交点的x
double ret = a.x;
double t = ((a.x - l.x) * (l.y - r.y) - (a.y - l.y) * (l.x - r.x))
/ ((a.x - b.x) * (l.y - r.y) - (a.y - b.y) * (l.x - r.x));
return ret + (b.x - a.x) * t;
}
vector<double> vec; //记录与雨滴的交点
vector<pii> res; //记录被雨滴打到的每个时间段
struct rain {
point o, a, b, c;
double r, h;
/* 雨滴三角形的三个点标号
* c
* /_\
* a b
*/
void in() {
scanf("%lf%lf%lf%lf", &o.x, &o.y, &r, &h);
a = o, b = o, c = o;
a.x -= r;
b.x += r;
c.y += h;
}
bool inside(const point &p) { //点是否在雨滴里面（包括边界）
return (dis(o, p) - eps < r && p.y - eps < o.y)
|| (cross(c, a, p) > -eps && cross(c, b, p) < eps
&& p.y > o.y + eps);
}
void intersectC() { //与雨滴的半圆 交 求交点
point b = s, d = e - s;
double A = d * d;
double B = (b - o) * d * 2;
double C = (b - o) * (b - o) - r * r;
double dlt = B * B - 4 * A * C;
if (dlt < -eps) return;
if (dlt < eps) dlt = 0; //消除dlt负数零的情况
else dlt = sqrt(dlt);
double t = (-B - dlt) / (2 * A);
point tp = b + d * t;
if (tp.x - eps < s.x && tp.x + eps > e.x && tp.y - eps < o.y) //因为是半圆，注意把没用的点判掉
vec.pb(tp.x);
t = (-B + dlt) / (2 * A);
tp = b + d * t;
if (tp.x - eps < s.x && tp.x + eps > e.x && tp.y - eps < o.y)
vec.pb(tp.x);
}
void intersectT() { //与雨滴的三角形 交 求交点 （水平的线段不算在其中）
double x;
if (segSegIntersect(a, c, s, e)) {
x = intersect(a, c, s, e);
if (x - eps > e.x && x + eps < s.x)
vec.pb(x);
}
if (segSegIntersect(c, b, s, e)) {
x = intersect(c, b, s, e);
if (x - eps > e.x && x + eps < s.x)
vec.pb(x);
}
}
void gao() {
vec.clear();
intersectC();
intersectT();
if (inside(s)) vec.pb(s.x);
if (inside(e)) vec.pb(e.x);
sort(vec.begin(), vec.end());
int cnt = unique(vec.begin(), vec.end()) - vec.begin();
if (cnt >= 2) //取最大和最小的两个交点 就是被雨滴打到的时间段 的 两端点
res.pb(mp(vec[0], vec[cnt - 1]));
}
} p;
int main() {
int i, j, cas;
scanf("%d", &cas);
for (int ca = 1; ca <= cas; ca++) {
scanf("%lf%lf%lf%lf%lf%d", &v1, &v2, &v, &t, &x, &n);
T = v1 * t / (v2 - v1) + t;
s.x = x;
s.y = 0;
e.x = x - v1 * T;
e.y = v * T;
ans = 0;
res.clear();
for (i = 0; i < n; i++) {
p.in();
p.gao();
}
//对每个时间段去重后计算答案
sort(res.begin(), res.end());
double r = e.x;
int SZ = res.size();
for (i = 0; i < SZ; i++) {
if (res[i].X - eps < r && r - eps < res[i].Y) {
ans += res[i].Y - r;
r = res[i].Y;
}
else if (r - eps < res[i].X) {
ans += res[i].Y - res[i].X;
r = res[i].Y;
}
}
printf("Case %d: %.4f\n", ca, ans / v1);
}
return 0;
}
补充：软件开发 , C++ ,
