ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1111. Squares

Very difficult solution (and some tests)
Posted by AleshinAndrei 25 Aug 2020 20:06
A could do the simple solution there I have 4 points of square and simple calculations of dist to this square. But i found this very easy and i figure out difficult formula for equations of the lines which bounding this square. I calculates dist for this lines and analyzing them.

This is initialization of square:
/*
void init(Point p1, Point p2){
int64_t dx = p1.x-p2.x, dy = p1.y-p2.y;
a = dx + dy; // some coof for line-equation
b = dx - dy;
c1 = dx*(p1.x-p1.y) + dy*(p1.x+p1.y);
c2 = dy*(p2.x-p2.y) - dx*(p2.x+p2.y);
dc = dx*dx + dy*dy; // delta between c-coof two parallel lines
if (dc == 0) {
// if square is dot
c1 = p1.x;
c2 = p1.y;
}
}
*/
There i calculate dists to lines
/*
if (dc == 0){
return std::hypot((p0.x - c1), (p0.y - c2));
} else {
double
d1 = (b*(p0.y) - a*(p0.x) + c1)/sqrt(2*dc), // signed dist to first line
d2 = (b*(p0.x) + a*(p0.y) + c2)/sqrt(2*dc), // signed dist to perpendicular to first line
d = sqrt(dc/2.0); // delta between two parallel lines (a side of square)
......
*/
"d" always is positive (if square isn't dot), bcs "(d1 - d) < d1" (dist to nearest line less than dist to farthest line)

there is some conditionals for calculate the dist to square
/*
if (d1 < 0) {
if (d2 < 0) {
// 1 corner   x1 = (c1*a - c2*b)/(2.0*dc), y1 = (-c1*b - c2*a)/(2.0*dc)
} else if(d2 <= d){
// 1 side
return fabs(d1);
} else {
// 2 corner   x2 = (c1*a - c2*b)/(2.0*dc) + (b/2.0), y2 = (-c1*b - c2*a)/(2.0*dc) + (a/2.0)
}
} else if (d1 <= d) {
if (d2 < 0){
// 2 side
return fabs(d2);
} else if(d2 <= d){
// inside square
return 0;
} else {
// 3 side
return fabs(d2 - d);
}
} else {
if (d2 < 0){
// 3 corner   x3 = (c1*a - c2*b)/(2.0*dc) - (a/2.0), y3 = (-c1*b - c2*a)/(2.0*dc) + (b/2.0)
} else if(d2 <= d){
// 4 side
return fabs(d1 - d);
} else {
// 4 corner   x4 = (c1*a-c2*b)/(2.0*dc) + (b-a)/2.0, y4 = (p0.y + (c1*b+c2*a)/(2.0*dc) + (a+b)/2.0
}
}
*/
after this we sorting dist with num, and print the answer

tests:
8
0 0 2 2
2 4 0 6
-8 -3 -8 -7
7 11 4 15
5 -5 9 -6
-2 -2 -2 -4
-4 6 -8 10
6 6 10 6
.....
6 2 : ans is "8 1 2 5 6 4 7 3"
0 0 : ans is "1 6 2 5 7 3 8 4"

Edited by author 26.08.2020 02:41
Re: Very difficult solution (and some tests)
Posted by alrh479 9 Jan 2022 18:33
I got acc but for test case "0 0"
it's not "1 6 2 5 7 3 8 4"
and i got "1 8 6 2 5 7 3 4"