|
|
back to boardVery difficult solution (and some tests) 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) 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" |
|
|