ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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"