Блог пользователя MarioYC

Автор MarioYC, 13 лет назад, По-английски

I'm getting WA #12 in this problem, what I do is take to points that are consecutive in the convex hull, then order all the other (N-2) points according to the measure of the angle we get of joining this point with the other two I chose at the beginning.



#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

struct point{
    long long x,y;
    long double ang;
    
    point(){}
    
    bool operator < (point X) const{
        return ang < X.ang;
    }
}P[5000];

bool ccw(point &A, point &B, point &C){
    return (A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x) >= 0;
}

long double dist(point &A, point &B){
    return sqrt((long double)(A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

int main(){
    int N;
    
    cin >> N;
    
    for(int i = 0;i < N;++i)
        cin >> P[i].x >> P[i].y;
    
    for(int i = 1;i < N;++i)
        if(P[i].x < P[0].x)
            swap(P[0],P[i]);
    
    for(int i = 2;i < N;++i)
        if(ccw(P[0],P[1],P[i]))
            swap(P[1],P[i]);
    
    long double a,b,c = dist(P[0],P[1]);
    
    for(int i = 2;i < N;++i){
        a = dist(P[i],P[0]);
        b = dist(P[i],P[1]);
        
        P[i].ang = (a*a + b*b - c*c) / (2 * a * b);
    }
    
    sort(P + 2,P + N);
    
    cout << P[0].x << " " << P[0].y << endl;
    cout << P[1].x << " " << P[1].y << endl;
    cout << P[(N + 1) / 2].x << " " << P[(N + 1) / 2].y << endl;
    
    return 0;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
As I know, this problem has a much simpler solution... Or do you want to solve it definitely in such way?..
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I would love finding my bug, but it is also interesting to hear about other solutions :)
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

it is simple you got WA because... your solution is wrong! surprisingly, is not it?

paint an example:

(0, 0), (1, 0) let's imagine this two point will be p[0] and p[1] after your sorting (i can't understand your sorting, but it is not matter)

(0, 1) // p[2]

(0, 2) // p[3]

(0, 3) // p[4]

you think that cirle must lie on poing p[3], but we can add two points: one with x < 0, and one with x > 0in such a way, that p[3] still be your "center" but in fact both of two added points can be inside cirlce or not.

UPD: but, maybe i am wrong, and you must to fix your compare function. what if all angles are the same? 

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    According to the input, there can't be three colinear points. Hence (0,0), (0,1), (0,2), (0,3) is invalid.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      O Key.

      (0,0), (0,1.0000013), (0,2.00000012312), (0,3.0000747) is OK ?

      There is only integers in input, but we can multyply all numbers by some constant and round them to the nearest integer. 

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Those 4 points are still on the same lime (x = 0).
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          i am bad. must be (0.0000001, 1), (0.00032,2),(-0.0013,3) ...
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ok, I tried this:

            N = 5
            5
            0 10000000
            0 0
            1 10000000
            3200 20000000
            -13000 30000000

            But I can't choose (0, 0), (0, 10000000) because that segment isn't on the convex hull.

            I get this solution

            -13000 30000000
            3200 20000000
            1 10000000
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Weird, changed from taking the leftmost point to taking the bottommost and got AC.

              for(int i = 1;i < N;++i)
                      if(P[i].y < P[0].y)
                          swap(P[0],P[i]);

              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                i have pointed to this place earlier
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  I still don't get why it fails, since there are at most two points with the same x. So, no matter which one I take, I'll get two points on the convex hull.
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится

                    there is two types of circle, one with center bellow than line (p[0], p[1]) and another with center upper that line. it can be problem? in my solution these cases processed separetely

                    • 13 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      I don't think that case would be a problem, since I work with the angles, and they are always in the upper part.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Also all angles can't be the same because there can't be 4 points on a circle.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      maybe you must to use radiuses instead of angles? i don't understand what angles do you use.

      for(int i = 1;i < N;++i)
      if(P[i].x < P[0].x)
        swap(P[0],P[i]);

      >>>>>

      for(int i = 1;i < N;++i)
        if(P[i].x < P[0].x ||   P[i].x == P[0].x  &&   P[i].y < P[0].y  )
      swap(P[0],P[i]);

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        That part is for choosing two points that are on the convex hull. I get two points A and B.

        Let's suppose the other N - 2 points are C1,C2, ..., CN-2 then I order using the cosines of the angles ACiB, which is the same as ordering the measures of the angles in decreasing order. So if I choose the Ci which is in the middle after ordering (call this D), it can be proven that the lower half is inside, and the upper half is outside of the circle. I mean the  circuncircle of A,B and D.

        This is because if an angle AXB (X being one of the points in the lower half of the ordering) is less than the angle ADB you can extend of the sides to a point Y such that the measure of AYB is equal to that of ADB, hence Y is on the circle and X is inside.

        A similar argument proves that points in the upper half of the ordering are outside the circle.