#include #include #include #include #include #include #include #include #include #include using namespace std; #define sqr(x) ((x)*(x)) #define eps 1e-8 #define Max 200000 struct pt{ double x,y; pt (double x,double y):x(x),y(y){} pt(){} double operator & (const pt &A) const{ return x*A.y-y*A.x; } pt operator -(const pt &A) const{ return pt(x-A.x,y-A.y); } pt operator +(const pt &A) const{ return pt(x+A.x,y+A.y); } }; struct line { double a; pt k, d; line() { } line(pt k, pt d) : k(k), d(d), a(atan2(k.y, k.x)) { } }; int sign(double x) { return (x > eps) - (x < -eps); } bool left(pt d, line j) { return sign(j.k & (d - j.d)) > 0; } bool right(pt d, line j) { return sign(j.k & (d - j.d)) < 0; } bool cmp(const line &i, const line &j) { int c = sign(i.a - j.a); if (c == 0) return left(i.d, j); return c < 0; } bool crossLine(line &i, line &j, pt &c) { double dm = j.k & i.k, ds = j.k & (j.d - i.d); if (sign(dm) == 0) { if (sign(ds)) return false; c = i.d; } else { double dt = ds / dm; c = pt(i.d.x + dt * i.k.x, i.d.y + dt * i.k.y); } return true; } pt cp[Max]; line L[Max]; int Q[Max], head, tail; bool getIntersection(line L[], int n, pt cp[], int &s, int &t) { sort(L, L + n, cmp); int m = 0; for (int i = 1; i < n; i++) if (sign(L[i].a - L[m].a)) L[++m] = L[i]; n = m + 1; Q[s = 0] = 0, Q[t = 1] = 1; if (!crossLine(L[0], L[1], cp[1])) return 0; for (int i = 2; i < n; i++) { while (s < t && right(cp[t], L[i])) t--; while (s < t && right(cp[s + 1], L[i])) s++; Q[++t] = i; if (!crossLine(L[Q[t - 1]], L[i], cp[t])) return 0; } for (bool f = true; f;) { f = false; while (s < t && right(cp[t], L[Q[s]])) t--, f = true; while (s < t && right(cp[s + 1], L[Q[t]])) s++, f = true; } if (!crossLine(L[Q[s]], L[Q[t]], cp[s])) return 0; return s + 1 < t;/*取等且答案可为一个点*/ } void out(line t){ printf("%lf %lf %lf %lf\n",t.d.x,t.d.y,t.k.x,t.k.y); } double calcD(pt a,pt b){ return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } int main(){ int i,j,N; double R; while(scanf("%d%lf",&N,&R)!=EOF){ for (i=0;ires){ res = D; resi = i,resj = j; } } printf("%.4lf %.4lf %.4lf %.4lf\n",cp[resi].x,cp[resi].y,cp[resj].x,cp[resj].y); } }