题:http://acm.hdu.edu.cn/showproblem.php?pid=4637
参考自：https://www.cnblogs.com/javawebsoa/p/3239001.html
#include<bits/stdc++.h> 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); } }sta,ed; 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; void in() { cin>>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 query1(){//与雨滴的半圆 交 求交点 point b=sta,d=ed-sta; 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<sta.x&&tp.x+eps>ed.x&&tp.y-eps<o.y) //因为是半圆，注意把没用的点判掉 vec.pb(tp.x); t=(-B+dlt)/(2*A); tp=b+d*t; if (tp.x-eps<sta.x&&tp.x+eps>ed.x&&tp.y-eps<o.y) vec.pb(tp.x); } void query2(){ //与雨滴的三角形 交 求交点 （水平的线段不算在其中,因为只算进和出，水平线不影响） double x; if(segSegIntersect(a,c,sta,ed)){ x=intersect(a,c,sta,ed); if(x-eps>ed.x&&x+eps<sta.x) vec.pb(x); } if(segSegIntersect(c,b,sta,ed)){ x=intersect(c,b,sta,ed); if(x-eps>ed.x&&x+eps<sta.x) vec.pb(x); } } void solve() { vec.clear(); query1(); query2(); ///判断起点终点有没有在当前点的范围内 if (inside(sta)) vec.pb(sta.x); if (inside(ed)) vec.pb(ed.x); sort(vec.begin(), vec.end()); int m=unique(vec.begin(), vec.end()) - vec.begin(); if(m>=2)//取最大和最小的两个交点就是被雨滴打到的时间段的两端点 res.pb(mp(vec[0],vec[m-1])); } }num; void init(){ } int main() { int cas; cin>>cas; for (int p=1;p<=cas;p++){ cin>>v1>>v2>>v>>t>>x>>n; T=v1*t/(v2-v1)+t; sta.x=x; sta.y=0; ed.x=x-v1*T; ed.y=v*T; ans=0; res.clear(); for(int i=0;i<n;i++){ num.in(); num.solve(); } sort(res.begin(), res.end()); double r=ed.x; for (int i=0;i<res.size();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 ",p,ans/v1); } return 0; }