Plot
National Olympiad — Regional round (2010 season)
Submission name: plot.cpp
Problem summary
Move the three vertices of a nondegenerate triangle from a protected 100×100 square into the eastern strip x≥100, 0≤y≤100. Preserve its area and reduce the sum of vertex movement distances. The original task scores valid outputs according to closeness to a minimum.
Source clarification. The original task explicitly gives 0–10 points for a valid layout according to closeness to optimal movement; it does not require a fixed textual answer. The implementation uses integer coordinates to avoid ambiguity in the three-decimal area tolerance.
Input
Three integer coordinate pairs, one per vertex.
Output
Three corresponding new coordinate pairs, each printed to three decimal places.
Constraints
Original coordinates are integers in [0,100]; area is strictly positive. The eastern strip is unbounded to the right.
Worked example
Official statement example.
Input
10 20 87 53 33 90
Output
100.000 20.000 166.157 53.000 100.000 90.000
Solution analysis
- A horizontal translation by 100−min(x) is always valid: it preserves area and puts every vertex in the eastern strip. Use it as a guaranteed feasible starting layout.
- The supplied heuristic improves this layout while preserving all y coordinates and requiring integer new x coordinates. Twice the signed area is linear in the three x coordinates. Enumerate the first two new x values and solve the resulting linear equation for the third; accept either orientation, since only absolute area matters.
- The current best movement S bounds every useful new x_i by original_x_i+S: all movements are eastward and contribute exactly new_x_i−original_x_i. Initially S≤300, so fewer than 301² first-two-coordinate pairs are needed per orientation. All tested coordinates are integers, making area preservation exact even after three-decimal output. This optimizes the restricted integer horizontal family, not the unrestricted geometric problem.
Why it works
The initial translation is feasible. Every accepted candidate has x≥100 and unchanged y in [0,100], and its determinant equals plus or minus the original determinant, so its area is exactly preserved. Only candidates with a lower sum of movements replace the current answer. Thus the final layout is valid and no worse than the initial translation. No claim of global minimum over arbitrary real vertex positions is made.
Watch out. This is an optimization heuristic and may receive partial rather than maximum score.,Reject nonintegral solutions of the determinant equation.,Output vertices in their original correspondence.
Commented C++17 solution
Valid-output optimization heuristic. It minimizes movement only among integer horizontal relocations; it does not guarantee the unrestricted optimum. Output may differ from the official illustrative output.
// Key idea: The initial translation is feasible. Every accepted candidate has x≥100 and unchanged y in
// [0,100], and its determinant equals plus or minus the original determinant, so its area is exactly
// preserved.
#include<algorithm>
#include<array>
#include<iomanip>
#include<iostream>
using namespace std;
int main(){
array<int,3>x{},y{},best{};
for(int i=0;i<3;++i){
cin>>x[i]>>y[i];
}
int shift=100-*min_element(x.begin(),x.end());
int bestCost=3*shift;
for(int i=0;i<3;++i){
best[i]=x[i]+shift;
}
int initialCost=bestCost;
int a=y[1]-y[2],b=y[2]-y[0],c=y[0]-y[1];
int area=a*x[0]+b*x[1]+c*x[2];
for(int u=100;u<=x[0]+initialCost;++u){
for(int v=100;v<=x[1]+initialCost;++v){
for(int sign:{-1,1}){
int remainder=sign*area-a*u-b*v;
int w=100;
if(c==0){
if(remainder!=0){
continue;
}
}
else{
if(remainder%c!=0){
continue;
}
w=remainder/c;
}
if(w<100){
continue;
}
int cost=u-x[0]+v-x[1]+w-x[2];
if(cost<bestCost){
bestCost=cost;
best={u,v,w};
}
}
}
}
cout<<fixed<<setprecision(3);
for(int i=0;i<3;++i){
cout<<double(best[i])<<' '<<double(y[i])<<'\n';
}
}