[editorial] Editorial - C. Nerd, or Not Nerd?

  • JongMan
    JongMan

    Nerd or Not Nerd

    Submissions: 48, accepted 3
    Fast Submission: Hate Practice ^ 3 (258분)
    AC Ratio: 6.25%
    Writer: JongMan
    이 문제는 제가 오랫동안 언젠가는 내야지 하고 별러왔던 문제입니다. 이렇게까지 낚시 문제가 될 줄은 몰랐는데 수많은 분들이 낚여서 입맛이 쓰네요 (...) 이 문제는 고전적인 문제이지만 쉽게 풀려면 풍부한 센스그리고 잘 준비된 기하 관련 prewritten 루틴들이 필요합니다. :) 
    기하라는 말에서 눈치채셨겠지만, 이 문제를 푸는 키포인트는 입력이 숫자 두 개라는 점을 이용해 이들을 2차원 평면에 플로팅하는 것입니다. 다음은 첫 번째 예제 입력을 2차원 평면에 플로팅한 것입니다.
    case_01a.PNG
    앗, 감이 오시나요? 네, A * [shoe size] + B * [typing speed] = F 인 직선을 그리면, 이 직선으로 이들 집합이 정확히 구분될 수 있어야겠죠! 이와 같이, 2차원 평면에 주어진 샘플 포인트를 가르는 직선을 찾을 수 있느냐는 문제를 linear separability 라고 합니다. (인공지능이나 기계학습 분야에서는 자주 언급되는 문제죠.)
    아, 물론 이 문제에서는 nerd score 가 T 이상인 사람은 무조건 nerd 고, T 미만은 일반인이라는 조건을 걸었기 때문에 문제가 달라진다고 생각할 수도 있죠. 하지만 A 와 B, F 의 부호를 모두 뒤집으면? 이 조건을 그대로 만족하게 됩니다. 따라서, 우리는 2차원 평면에서 점들을 완전히 구분할 수 있는 직선을 찾는 데 집중할 수 있습니다.
    이 기하 문제의 해답은 여러 가지가 있겠지만, 저희가 의도한 방법은 볼록 껍질(Convex Hull) 을 이용하는 것입니다. 만약 두 종류의 정점을 갈라놓을 수 있는 직선이 있다면, 이들은 각 종류 정점들의 볼록 껍질 또한 구분할 수 있지요. 그리고, 두 개의 볼록 다각형은, 서로 겹치거나 닿아 있지만 않다면 이들을 구분할 방법이 반드시 존재합니다.
    따라서, 볼록 껍질을 구하고 이들의 충돌 여부를 구하면 이 문제를 풀 수 있습니다. 볼록 다각형의 충돌을 검사하기 위해서는 다음과 같은 과정을 거쳐야 합니다.
    1. 각 다각형의 모든 선분들에 대해, 다른 다각형의 선분과 교차하거나 닿아 있다면 충돌
    2. 각 다각형의 모든 점에 대해, 다른 다각형에 포함되어 있거나 닿아 있다면 충돌
    실제 대회때는 여기까지 다 온 후에도 2번 체크를 까먹으신 분들이 많은데요, 다각형의 선분이 하나도 교차하지 않더라도 하나가 다른 하나에 포함되어 있을 수도 있죠. :) 
    아이디어만 맞게 잡고 위에 설명한 코드만 정확하게 구현하셨으면 별다른 문제 없이 풀 수 있으셨을 거라고 생각합니다. 세 점이 한 직선 상에 있다거나, convex hull 이 면적이 없다거나 하는 예외 케이스도 있을 수 있겠지만, 데이터에서는 일부러 그런 경우를 제외하도록 했으니 튼튼한 기하 기반 라이브러리가 있다면 쉽게 해결할 수 있을 거라고 생각합니다.
    아래는 레퍼런스 소스 코드입니다.
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
    #define REP(i,n) FOR(i,0,n)
    #define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
    #define pb push_back
    #define all(x) (x).begin(),(x).end()
    #define CLEAR(x,with) memset(x,with,sizeof(x))
    #define sz size()
    typedef long long ll;
    struct Point
    {
    int y, x;
    Point(int y_ = 0, int x_ = 0) : y(y_), x(x_) {}
    bool operator < (const Point& b) const { if(y != b.y) return y < b.y; return x < b.x; }
    bool operator == (const Point& b) const { return y == b.y && x == b.x; }
    Point operator - (const Point& b) const { return Point(y - b.y, x - b.x); }
    double norm() const { return hypot(y, x); }
    };
    int ccw(const Point& a, const Point& b, const Point& c)
    {
    int by = b.y - a.y, bx = b.x - a.x;
    int cy = c.y - a.y, cx = c.x - a.x;
    return bx * cy - cx * by;
    }
    struct Comparator
    {
    Point o;
    Comparator(const Point& pivot) : o(pivot) {}
    bool operator () (const Point& a, const Point& b) const
    {
    int v = ccw(o, a, b);
    if(v > 0) return true;
    if(v < 0) return false;
    return (a-o).norm() < (b-o).norm();
    }
    };
    // note: this doesn't handle inputs which has degenerate convex hull such as:
    // { (1,1), (2,2), (3,3) }
    vector grahamScan(vector p)
    {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    if(n < 3) return p;
    Comparator comp(p[0]);
    sort(p.begin() + 1, p.end(), comp);
    p.push_back(p[0]);
    vector r;
    r.reserve(n/2);
    r.push_back(p[0]);
    r.push_back(p[1]);
    for(int i = 2; i <= n; ++i)
    {
    while(r.size() > 1 && ccw(r[r.size()-2], r[r.size()-1], p[i]) <= 0)
    r.pop_back();

    r.push_back(p[i]);
    }
    r.pop_back();
    return r;
    }
    bool withinBounds(const Point& a, const Point& b, const Point& p)
    {
    return
    min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
    min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y) ;
    }
    // returns true iff a is inside convex polygon p or touches p
    bool insideConvex(const vector& p, const Point& a)
    {
    int plus = 0, minus = 0;
    for(int i = 0; i < p.size(); ++i)
    {
    int j = (i+1) % p.size();
    int det = ccw(p[i], p[j], a);
    if(det == 0)
    return withinBounds(p[i], p[j], a);
    if(det < 0) ++minus; else ++plus;
    if(plus && minus) return false;
    }
    return true;
    }
    int sgn(int x) { if(x == 0) return 0; return (x < 0 ? -1 : 1); }
    // returns true iff segments (p1, p2) and (p3, p4) touch each other
    // direct implementation of CLRS 2nd SEGMENTS-INTERSECT.
    bool intersects(const Point& p1, const Point& p2, const Point& p3, const Point& p4)
    {
    int d1 = sgn(ccw(p3, p4, p1)), d2 = sgn(ccw(p3, p4, p2));
    int d3 = sgn(ccw(p1, p2, p3)), d4 = sgn(ccw(p1, p2, p4));
    if(d1 * d2 < 0 && d3 * d4 < 0) return true;
    if(d1 == 0 && withinBounds(p3, p4, p1)) return true;
    if(d2 == 0 && withinBounds(p3, p4, p2)) return true;
    if(d3 == 0 && withinBounds(p1, p2, p3)) return true;
    if(d4 == 0 && withinBounds(p1, p2, p4)) return true;
    return false;
    }
    // returns true iff two convex polygons touch each other, or intersect, or one is inside of the other
    bool collides(const vector& a, const vector& b)
    {
    for(int i = 0; i < a.size(); ++i)
    if(insideConvex(b, a[i])) return true;
    for(int i = 0; i < b.size(); ++i)
    if(insideConvex(a, b[i])) return true;
    for(int i = 0; i < a.size(); ++i)
    for(int j = 0; j < b.size(); ++j)
    if(intersects(a[i], a[(i+1)%a.size()], b[j], b[(j+1)%b.size()]))
    return true;
    return false;
    }
    int main()
    {
    int cases;
    cin >> cases;
    for(int cc = 0; cc < cases; ++cc)
    {
    int n;
    cin >> n;
    vector a, b;
    for(int i = 0; i < n; ++i)
    {
    int p, y, x;
    cin >> p >> y >> x;
    if(p == 0)
    a.push_back(Point(y, x));
    else
    b.push_back(Point(y, x));
    }
    a = grahamScan(a);
    b = grahamScan(b);
    if(collides(a, b))
    cout << "THEORY IS INVALID" << endl;
    else
    cout << "THEORY HOLDS" << endl;
    }
    }

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
5개의 댓글이 있습니다.
  • Stun
    Stun

    저는 처음에 접근한게 nerd 한 경우와 nerd 하지 않은경우 2가지로 나눠서 .. 각각의 i 와 j 에 대해서 서로 - 연산을 해서 나온 모든 식이 >0이 되게 하는 A B 가 존재하는가 로 접근 하다가 이를 구할 방법이 떠오르지 않아 쥐쥐 쳤습니다 -_-
    컨벡스홀.. 역시 알고리즘을 아는게 다가 아닌가봅니다 -_-;; ㅠ_ㅠ


    15년 전 link
  • JongMan
    JongMan

    네.. ^^ 프로그래밍 대회를 처음 준비하기 시작할 때는 알고리즘을 '배우는' 것이 중요하지만, 시간이 지날수록 문제를 적절히 변환하고 아는 알고리즘을 이용하는 능력이 중요해지죠. 특히, 어떠한 형식으로든 입력을 시각화하는 것은 문제에 대한 많은 직관을 제공할 수 있기 때문에 특히 큰 도움이 됩니다.
    시각화가 중요하다는 점에서 저는 굉장히 좋은 문제였다고 생각해요~ :D


    15년 전 link
  • nocut98
    nocut98

    흡 저는 그냥 원점에서 직선을 그어서 상한/하한으로 풀어볼려고 했는데, 테스트를 해볼 수 없을까요?


    15년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    몇년 전 로키마운틴 리저널에 나왔던 문제랑 비슷한데요, 아마 알고스팟에서도 그 문제로 모의고사를 했던 걸로 기억합니다.
    유키님이 해법을 쓰셨던 걸로 기억하는데...
    모든 점의 각도를 조금씩 돌려보며 수평선으로 나뉘어질 수 있는지 검사해서 풀었다고 쓰셨던 것 같아요.


    15년 전 link
  • Being
    Being

    이 문제(determine whether two sets of points are separable by a line)는 1978년 Shamos M. I.의 Ph.D. 논문에서 다뤄졌다고 합니다.
    관심있으신분은 찾아보시길..
    Shamos, M. I. (1978), Computational geometry, PhD thesis, Yale Univ., New Haven. UMI #7819047


    15년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.