Proficient.
Put your skills to the test.

Problem summary

A jump reflects one labeled point through another. Produce jumps arranging labels 1…N counterclockwise around a convex polygon, the best graded configuration. Points initially have no collinear triple.

Constraints

3 ≤ N ≤ 100; initial coordinates 0…200; at most 30,000,000 jumps; final coordinate absolute values at most 2^31.

Worked example

The official witness above is nonunique. The deterministic code prints a different valid configuration C; the local validator checks the resulting geometry, jump limit, and coordinate bound.

6
3 5
4 3
3 1
11 4
7 7
7 2

6
3 1
3 2
3 6
3 4
6 2
6 1

Solution analysis

1. Two reflections of point P, first about A and then about B, translate P by 2(B−A). Keep points 1 and 2 fixed. If necessary reflect point 3 about point 2 to orient the first triangle positively. Let E=P2−P1 and W=P3−P2; their determinant D is positive.
2. Use affine coordinates P=P1+uE+vW, storing the integer numerators U=uD and V=vD. Points 1,2,3 have coordinates (0,0),(1,0),(1,1). For each subsequent point, paired reflections about points 2 and 3 change v by two. Choose v in [previous v+2,previous v+4). Paired reflections about points 1 and 2 then change u by two. Choose the largest such u that makes the new chain edge turn strictly counterclockwise. Integer floor division with a strict numerator bound avoids floating point.
3. The ratios Δu/Δv of successive edges strictly decrease, starting from the vertical edge 2→3. The chain bends left, and its final edge back to point 1 also turns positively. For the official example the published six jumps give a valid weakly convex configuration C; this program instead emits a deterministic strictly convex construction, so its witness differs. It computes only O(N) repeated-pair commands before printing the jumps.

Why it works

Positive affine determinant preserves orientation. Each newly chosen height increases strictly and each edge slope Δu/Δv strictly decreases, so the chain from point 2 is strictly convex and has no intersections. Every later slope is negative; at the final point its last slope is smaller than the weighted average slope from point 1, proving the closing turn is positive. The turn at point 1 is positive because the final height is positive, and the turn at point 2 is positive by construction. Thus all labels form a strictly convex counterclockwise polygon. Reflection pairs realize precisely the affine translations. For bounds, initial |u|,|v|≤80,000/D≤80,000. Heights stay below 4N and each horizontal edge slope decreases by at most one because its height increment is at least two. Hence |u|<4N² and final coordinates have magnitude below 9,000,000. At most 40,200 vertical and 60,001 horizontal translation pairs per moved point suffice, giving fewer than 20,000,000 jumps for N≤100, within the required 30,000,000.

Watch out. Use mathematical floor division for negative numerators. A jump moves only its first index. Do not store millions of pairs: store repeated commands, then stream them. The best result is counterclockwise label order, not an arbitrary convex hull.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
using Integer=long long;
struct Point{
    Integer x,y;
};
Point operator-(Point a,Point b){
    return {a.x-b.x,a.y-b.y};
}
Integer cross(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
Integer floorDivide(Integer a,Integer b){
    Integer quotient=a/b;
    if(a%b<0){
        quotient--;
    }
    return quotient;
}
struct Command{
    int moving,first,second;
    Integer repetitions;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Point>points(n);
    for(Point&point:points){
        cin>>point.x>>point.y;
    }
    vector<Command>commands;
    Integer jumps=0;
    if(cross(points[1]-points[0],points[2]-points[1])<0){
        points[2]={2*points[1].x-points[2].x,2*points[1].y-points[2].y};
        commands.push_back({3,2,0,1});
        jumps++;
    }
    Point horizontal=points[1]-points[0];
    Point upward=points[2]-points[1];
    Integer determinant=cross(horizontal,upward);
    vector<Integer>u(n),v(n);
    for(int i=0;i<n;i++){
        u[i]=cross(points[i]-points[0],upward);
        v[i]=cross(horizontal,points[i]-points[0]);
    }
    auto translate=[&](int moving,int first,int second,Integer count){
        if(count==0){
            return;
        }
        if(count<0){
            swap(first,second);
            count=-count;
        }
        commands.push_back({moving+1,first+1,second+1,count});
        jumps+=2*count;
    };
    for(int i=3;i<n;i++){
        // Affine height increases by between two and four lattice units.
        Integer vertical=-floorDivide(v[i]-v[i-1]-2*determinant,2*determinant);
        translate(i,1,2,vertical);
        v[i]+=2*determinant*vertical;
        Integer previousHeight=v[i-1]-v[i-2];
        Integer nextHeight=v[i]-v[i-1];
        Integer previousWidth=u[i-1]-u[i-2];
        // Largest horizontal translate that makes this turn strictly positive.
        Integer numerator=previousWidth*nextHeight-(u[i]-u[i-1])*previousHeight-1;
        Integer horizontalSteps=floorDivide(numerator,2*determinant*previousHeight);
        translate(i,0,1,horizontalSteps);
        u[i]+=2*determinant*horizontalSteps;
    }
    cout<<jumps<<'\n';
    for(const Command&command:commands){
        for(Integer i=0;i<command.repetitions;i++){
            cout<<command.moving<<' '<<command.first<<'\n';
            if(command.second!=0){
                cout<<command.moving<<' '<<command.second<<'\n';
            }
        }
    }
}