#include using namespace std; typedef long long int ll; typedef double ld; typedef vector vi; // push_back insert lower_bound upper_bound erase #define F(a) for ( ll i = 0; i < (ll)(a); ++i ) #define EPS (1e-8) bool eq(ld a, ld b) { return fabs(a-b) <= fabs(a+b) * EPS; } struct Pt{ ld x, y; ll flag; bool operator <(const Pt &p) const { return x < p.x-EPS || (eq(x, p.x) && y < p.y-EPS); } Pt operator+(const Pt &p){ return{x+p.x, y+p.y}; } Pt operator-(const Pt &p){ return{x-p.x, y-p.y}; } Pt operator-(){ return{-x, -y}; } Pt operator*(ld d){ return {x*d, y*d}; } Pt operator/(ld d){ return {x/d, y/d}; } friend ostream &operator<<(ostream &os, const Pt &a){ os<>(istream &is, Pt &a){ is>>a.x>>a.y; return is; } }; struct Line { Pt a, b; bool operator<(Line &l){ Pt v=b-a, w=l.b-l.a; return atan2(v.y, v.x) < atan2(w.y, w.x); } }; struct Cir { Pt s; ld r; Pt point(double a)const{ return {s.x+cos(a)*r, s.y+sin(a)*r}; } bool operator<(const Cir &a){ return r0)return 0; Pt dv = line_point_closest_point(b, a.s); ld d = norm(dv-a.s); ld h = sqrt(a.r*a.r-d*d); Pt n = scale_to(b.b-b.a, h); p1 = dv+n; p2 = dv-n; return 1+!(eq(p1.x, p2.x) && eq(p1.y, p2.y)); // returns the number of intersections } ll solve(ll N, ld R, Line l, vector a){ for(Cir &p:a) p.r = R+0.00001; vector p; F(N){ Pt q, w; ll e = circle_line_intersection(a[i], l, q, w); if(e){ q.flag = +1; w.flag = -1; p.push_back(q); p.push_back(w); } } sort(p.begin(), p.end()); //for(Pt q:p)cerr<> N >> R >> l.b; vector a(N); for(Cir &p:a) cin >> p.s; ll mx=solve(N, R, l, a); //ll mx2=solve(N, R+0.00101, l, a); // safe margin //assert(mx==mx2); cout<