Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <ctime>
- #include <cassert>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define all(v) v.begin(), v.end()
- #define pii pair<int,int>
- #define vi vector<int>
- #define ll long long
- #ifdef WIN32
- #define I64 "%I64d"
- #else
- #define I64 "%lld"
- #endif
- const double eps = 1e-12;
- struct Point {
- double x, y, r;
- Point () {}
- Point(double xx, double yy) {
- x = xx; y = yy;
- }
- void read() {
- scanf("%lf%lf", &x, &y);
- }
- void readc() {
- scanf("%lf%lf%lf", &x, &y, &r);
- }
- Point operator - (Point a) {
- return Point(x - a.x, y - a.y);
- }
- Point operator + (Point a) {
- return Point(x + a.x, y + a.y);
- }
- double operator * (Point a) {
- return x * a.y - y * a.x;
- }
- void makeLen(double len) {
- double l = sqrt(x * x + y * y);
- x /= l; y /= l;
- x *= len; y *= len;
- }
- double scal(Point p) {
- return x * p.x + y * p.y;
- }
- };
- Point circ[1000000];
- int n;
- Point p, q;
- pair<double, int> A[1000000];
- int An;
- int comp(double a, double b) {
- if (fabs(a - b) < eps) return 0;
- if (a - b > eps) return 1;
- return -1;
- }
- void getLine(double &a, double &b, double &c, Point p, Point q) {
- a = p.y - q.y;
- b = q.x - p.x;
- c = -(a * p.x + b * p.y);
- }
- vector<Point> getInter(double a, double b, double c, Point circ) {
- vector<Point> ans;
- double dist = fabs(a * circ.x + b * circ.y + c);
- if (comp(dist, circ.r) >= 0) return ans;
- Point norm = Point(a, b);
- Point p;
- if (comp(a, 0) != 0) p = Point(-c / a, 0); else
- p = Point(0, -c / b);
- if (comp(norm.scal(circ - p), 0) > 0) norm.x *= -1, norm.y *= -1;
- norm.makeLen(dist);
- p = circ + norm;
- Point vec = Point(-b, a);
- vec.makeLen(sqrt(circ.r * circ.r - dist * dist));
- ans.pb(vec + p);
- ans.pb(p - vec);
- return ans;
- }
- int main() {
- freopen("horseraces.in","r",stdin);
- freopen("horseraces.out","w",stdout);
- p.read(); q.read();
- scanf("%d", &n);
- for (int i = 0; i < n; ++i)
- circ[i].readc();
- double a, b, c;
- getLine(a, b, c, p, q);
- double d = sqrt(a * a + b * b);
- a /= d; b /= d; c /= d;
- Point dv = q - p;
- dv.makeLen(1);
- for (int i = 0; i < n; ++i) {
- vector<Point> tmp = getInter(a, b, c, circ[i]);
- if (tmp.size() != 2) continue;
- double t1, t2;
- if (comp(dv.x, 0) != 0) {
- t1 = (tmp[0].x - p.x) / dv.x;
- t2 = (tmp[1].x - p.x) / dv.x;
- } else {
- t1 = (tmp[0].y - p.y) / dv.y;
- t2 = (tmp[1].y - p.y) / dv.y;
- }
- if (comp(t1, t2) > 0) swap(t1, t2);
- A[An++] = mp(t1, 0);
- A[An++] = mp(t2, 1);
- }
- sort(A, A + An);
- int op = 0;
- double ans = 0;
- for (int i = 0; i < An; ++i) {
- if (op > 0) ans += A[i].f - A[i - 1].f;
- if (A[i].s == 0) ++op; else
- --op;
- }
- printf("%.6lf", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment