2139A — Maple and Multiplication

2139B — Cake Collection

2138A — Cake Assignment

2138B — Antiamuny Wants to Learn Swap

2138C1 — Maple and Tree Beauty (Easy Version)

2138C2 — Maple and Tree Beauty (Hard Version)

2139D — Antiamuny and Slider Movement

2139E1 — Determinant Construction (Easy Version)

2139E2 — Determinant Construction (Hard Version)

2139F — Ode to the Bridge Builder

For convenience, we mark the targets point and the points on the initial segment with $$$A(0,0),B(1,0),C(p,q)$$$.

The problem asks us to do at most $$$\left\lceil 2|AC|\right\rceil$$$ moves. This constraint is actually not quite usual. We can first show that the theoretical lower bound should be $$$x=\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1$$$. We can show we can't get less moves by following: If we have already constructed the final structure, then $$$AC$$$ and $$$BC$$$ should be connected with a path, and we can find a path from $$$A$$$ to $$$C$$$ and a path from $$$B$$$ to $$$C$$$ that don't intersect (except at point $$$C$$$), otherwise the structure can't be built with non-degenerate triangles.

And we have to alternate progressing through two paths every time we construct a triangle, otherwise we must draw a line longer than $$$1$$$. The last triangle will cover both paths, so the number of steps will be decreased by one. The optimal path is two straight segments (which is not always possible).

\textbf{Case 1.1:} We first try some simple strategies. Two triangles can form a parallelogram, so we can connect $$$AC$$$, choose a point $$$D$$$ on $$$AC$$$ which makes $$$|AD|=\frac{|AC|}{\lceil|AC|\rceil}$$$, which is always in range $$$[0.5,1]$$$ when $$$|AC|\ge 1$$$. And from $$$\triangle ADB$$$ we can construct a parallelogram. We draw a line passing $$$D$$$ that is parallel to $$$AB$$$, a line passing $$$B$$$ that is parallel to $$$AC$$$, and they intersects at $$$E$$$. Then we pile up the same parallelogram structure until we reach $$$C$$$. This always works when $$$30^\circ\le\angle CAB\le60^\circ$$$.

Proof: We first prove that all segments has length between $$$0.5$$$ and $$$1$$$. Because we stack the same parallelogram structure, all segments have length equal to $$$AB,BD$$$ or $$$AD$$$. $$$AB$$$ and $$$AD$$$ already meets the requirement. When $$$30^\circ\le\angle CAB\le60^\circ$$$, the length of $$$BD$$$ is at least $$$0.5$$$ as the distance between two parallel lines is at least $$$0.5$$$, and at most $$$1$$$ as $$$AB=1$$$ and $$$\angle CAB$$$ is never the largest angle in $$$\triangle DAB$$$. We can calculate that the number of moves we used is $$$2\left\lceil |AC|\right\rceil-1\le\left\lceil 2|AC|\right\rceil$$$ which matches the requirement (for the last parallelogram we only need one triangle).


\textbf{Case 1.2:} We can change the way we construct parallelograms (with sides $$$AB,BC$$$) and this method always works when $$$30^\circ\le\angle CBx\le60^\circ$$$. The number of moves is $$$\left\lceil2|BC|\right\rceil\le \left\lceil 2|AC|\right\rceil$$$. This case is actually necessary, which will be explained in the following part.


\textbf{Case 2:} If $$$\angle CAB \lt \angle CBx \lt 30^\circ$$$. We first build a point $$$D$$$ which makes $$$AD=1$$$ and $$$\angle DAB=30^\circ$$$ and construct $$$\triangle DAB$$$.

We can show that the constraint is actually easier to meet in this situation, because when $$$\angle CAB \lt \angle CBx \lt 30^\circ$$$, $$$|BC| \lt |AC|-0.5$$$. With this, $$$\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1=\left\lceil 2|AC|\right\rceil-1$$$ always holds, allowing us one extra move.

Then we draw a line passing $$$D$$$ parallel to $$$BC$$$. We can show that if $$$\angle DAB=30^\circ$$$ and $$$0\le \angle CAB\le 30^\circ$$$, the distance from $$$D$$$ to line $$$BC$$$ is at least $$$0.5$$$. So all segments with ends on different lines will have length $$$\ge 0.5$$$.

Then we select a point $$$E$$$ on $$$BC$$$, which makes $$$DE=1$$$. We can show that $$$\sqrt{3}-1\le |BE|\le 1$$$ based on some calculations in this case. Then we do a similar parallelogram construction process to $$$C$$$. The total number of moves is $$$2\left\lceil |CE|\right\rceil+2$$$.

There are still two cases here to analyze to prove the number of steps fulfills our requirement. We write $$$|BC|=a+b$$$ where $$$a$$$ is the integer part of $$$|BC|$$$, then we analyze cases about $$$b$$$.

• Case 2.1: When $$$b\ge\sqrt{3}-1$$$ or $$$b=0$$$, we can show that $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$, and $$$\left\lceil |AC|\right\rceil=\left\lceil |BC|\right\rceil+1$$$ if $$$|AC|\ge 2$$$. The number of steps is $$$2\left\lceil |EC|\right\rceil+2\le 2\left\lceil |BC|\right\rceil+2=2\left\lceil |AC|\right\rceil$$$.

• Case 2.2: When $$$0 \lt b \lt \sqrt{3}-1$$$, we can show that $$$\left\lceil |EC|\right\rceil=\left\lceil |BC|\right\rceil-1$$$. Total moves equals to $$$2+2\left\lceil |CE|\right\rceil=2\left\lceil |BC|\right\rceil\le \left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$.

Be careful with small cases where $$$|BC|$$$ is too short, which may make $$$|DF|=|EG| \lt 0.5$$$.

Note that there are some cases where $$$\angle CBx \gt 30^\circ$$$ and $$$\angle CAB \lt 30^\circ$$$, where Case 2 strategy doesn't work. So case 1.2 is required.


\textbf{Case 3:} If $$$\angle CBx \gt \angle CAB \gt 60^\circ$$$. We first build a point $$$D$$$ which makes $$$AD=1$$$ and $$$\angle DAB=60^\circ$$$ and construct $$$\triangle DAB$$$. We write $$$|AC|=a+b$$$ where $$$a$$$ is integer, then we analyze two cases about $$$b$$$.

• \textbf{Case 3.1:} When $$$b \gt 0.5$$$ or $$$b=0$$$, $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$. We begin a same parallelogram construction as Case 1 where the sides of parallelogram are $$$BC,BD$$$. We can show that $$$30^\circ\le\angle CBD\le60^\circ$$$. So it is possible to pile up to $$$C$$$ from $$$BD$$$ in $$$2\left\lceil |BC|\right\rceil-1$$$ moves. And in total we need $$$2\left\lceil |BC|\right\rceil\le2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$ moves.


• \textbf{Case 3.2:} When $$$0 \lt b\le 0.5$$$, $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil+1$$$. We instead connect $$$CD$$$ and construct parallelogram with sides $$$DC,DB$$$. We can show that $$$120^\circ\le\angle CDB\le150^\circ$$$ so we can still do the parallelogram construction. When $$$|AC|\ge \sqrt{3}$$$, $$$\left\lceil |CD|\right\rceil=\left\lceil |AC||\right\rceil-1$$$, making the number of moves $$$2\left\lceil |CD|\right\rceil+1=2\left\lceil |AC|\right\rceil-1=\left\lceil 2|AC|\right\rceil$$$.


Actually case 1.1 is not required, because it is impossible to construct a testcase where $$$\angle CAB \lt 60^\circ, \angle CBx \gt 60^\circ,0 \lt b\le 0.5$$$ and Case 3.2 fails.

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db pi = acos(-1.0);
const int N = 1000005;

inline int sgn(db x){
    if(x < 1e-13 && x > -1e-13) return 0;
    if(x > 0) return 1;
    return -1;
}

struct point{
    db x,y;
    point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {}
};
point operator + (const point &p1,const point &p2){
	return point(p1.x + p2.x,p1.y + p2.y);
}
point operator - (const point &p1,const point &p2){
	return point(p1.x - p2.x,p1.y - p2.y);
}
point operator * (db x,const point &p){
	return point(x * p.x,x * p.y);
} 
bool operator == (point x,point y){
	return sgn(x.x - y.x) == 0 && sgn(x.y - y.y) == 0;
}

inline db dot(point p1,point p2){
    return p1.x * p2.x + p1.y * p2.y;
}

inline db det(point p1,point p2){
	return p1.x * p2.y - p2.x * p1.y;
}

inline db len(point p){
    return sqrtl(1.0 * p.x * p.x + 1.0 * p.y * p.y);
}

point project_point(point x,point ya,point yb){
	point v = yb - ya;
	return ya + (dot(v,x - ya) / dot(v,v)) * v;
}

db distp(point x,point ya,point yb){
	return fabs(det(ya - x,yb - x)) / len(yb - ya);
}

point line_circle_intersec_point(point o,point la,point lb){
	db dis = distp(o,la,lb),l;
	point pj = project_point(o,la,lb);
	l = sqrt(1.0 - dis * dis);
	point ret = pj + (l / len(lb - la)) * (lb - la);
	return ret;
}

tuple <int,int,int> ans[N];
point p[N],target;
int step;

bool check(int n){
    set <pair <int,int> > st;
    st.insert({1,2});
    if(n > step) return 0;
    db eps_len = 1e-8,eps_dis = 1e-4;
    int fl = 0;
    for(int i = 1;i <= n;i ++){
        auto [u,v,w] = ans[i];
        if(u > v) swap(u,v);
        if(st.find({u,v}) == st.end()) return 0;
        if(len(p[u] - p[w]) < 0.5 - eps_len || len(p[u] - p[w]) > 1.0 + eps_len) return 0;
        if(len(p[v] - p[w]) < 0.5 - eps_len || len(p[v] - p[w]) > 1.0 + eps_len) return 0;
        st.insert({u,w}); st.insert({v,w});
        if(len(p[w] - target) <= eps_dis) fl = 1;
    }
    return 1;
}

int solve1a(){
    point dir = target - p[1];
    int split = ceil(len(dir) - 1e-9);
    int c = 2;
    for(int i = 1;i < split;i ++){
        ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        // construct one parallelogram
    }
    ++ c; p[c] = target;
    ans[c - 2] = {c - 2,c - 1,c};
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve1b(){
    point dir = target - p[2];
    int split = ceil(len(dir) - 1e-9);
    int c = 2;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve2(){
    p[3] = point(sqrt(3.0) / 2,0.5);
    p[4] = line_circle_intersec_point(p[3],p[2],target);
    if(len(p[4] - p[2]) > 1)
        p[4] = p[2] + (1.0 / len(target - p[2])) * (target - p[2]);
    ans[1] = {1,2,3};
    ans[2] = {2,3,4};
    point dir = target - p[4];
    int split = ceil(len(dir) - 1e-9);
    int c = 4;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[4] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve3a(){
    p[3] = point(0.5,sqrt(3.0) / 2);
    ans[1] = {1,2,3};
    point dir = target - p[2];
    int split = ceil(len(dir) - 1e-9);
    int c = 3;
    for(int i = 1;i < split;i ++){
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    ++ c; p[c] = target;
    ans[c - 2] = {c - 2,c - 1,c};
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve3b(){
    p[3] = point(0.5,sqrt(3.0) / 2);
    ans[1] = {1,2,3};
    point dir = target - p[3];
    int split = ceil(len(dir) - 1e-9);
    int c = 3;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve(){
    if(int res = solve1a()) return res;
    if(int res = solve1b()) return res;
    if(int res = solve2()) return res;
    if(int res = solve3a()) return res;
    if(int res = solve3b()) return res;
    return 0;
}

int main(){
    int TC; scanf("%d",&TC);
    p[1] = point(0,0);
    p[2] = point(1,0);
    while(TC --){
        int tx,ty;
        scanf("%d %d %d",&tx,&ty,&step);
        step = ceil(2.0 * sqrt(1.0 * tx * tx + 1.0 * ty * ty));
        target = point(tx,ty);
        int n = solve();
        assert(n > 0);
        printf("%d\n",n);
        for(int i = 1;i <= n;i ++){
            auto [u,v,w] = ans[i];
            printf("%d %d %.12lf %.12lf\n",u,v,p[w].x,p[w].y);
        }
    }
    return 0;
}