[editorial] 오늘의 하드풀기: SRM373 Div 1 Hard, SpiralConstruction

  • JongMan
    JongMan

    오늘의 토론 문제는 오늘 열렸던 SRM373 Hard 인 SpiralConstruction 입니다.
    [문제 보기]
    토론은 댓글이나 답글로 해주세요~ ^^

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

    17년 전
9개의 댓글이 있습니다.
  • JongMan
    JongMan

    크와아앙 풀었따;;; 아 이렇게 어렵게 풀다니 엉엉 ㅠㅠ


    17년 전 link
  • legend12
    legend12

    풀었음~ 다소 간단하게 푼것 같긴 한데.. CCW 에서 오버플로우 나는것 때문에 삽질을 -_-;;;


    17년 전 link
  • legend12
    legend12

    소스코드는 여기에~
    http://rafb.net/p/XrV6v062.html


    17년 전 link
  • JongMan
    JongMan

    소스코드는 댓글에 인용에 접기 옵션 써서 올려주세요~ rafb 는 하루 지나면 지워져요~
    근데 그분은 백트로 푸셨군 ㅎㄷㄷ 저는 dp라능.. 내일 소스코드 올리겠다능..


    17년 전 link
  • astein
    astein

    에디토리얼에 (소스코드 포함) 올렸다는 [...]


    17년 전 link
  • legend12
    legend12

    댓글에 접기 인용이 가능하다는걸 몰랐군 ㅎㄷㄷ
    [spoiler="소스코드"][code c++]#include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #define max(a, b) (a > b ? a : b)
    #define min(a, b) (a < b ? a : b)
    //#define abs(a) (a < 0 ? -(a) : a)
    #define sqr(a) ((a) * (a))
    #define eps 1.0e-9
    #define pi (2.0 * acos(0.0))
    #define sz(a) ((int)a.size())
    #define clr(a, b) (memset(a, b, sizeof(a)))
    //#define pb push_back
    #define MAKEONE(a) ((a) == 0 ? a : (a) / abs(a))
    using namespace std;
    typedef long long ll;
    typedef vector VI;
    typedef vector VS;
    typedef vector VD;
    typedef set SI;
    struct point {
    int x, y;
    };
    struct line {
    point pa, pb;
    };
    int ccw(point pa, point pb, point pc) {

    return MAKEONE((pa.x - pb.x) * (pb.y - pc.y) - (pb.x - pc.x) * (pa.y - pb.y));
    }

    bool InLine(line l, point p) {

    if (min(l.pa.x, l.pb.x) <= p.x && p.x <= max(l.pa.x, l.pb.x) && min(l.pa.y, l.pb.y) <= p.y && p.y <= max(l.pa.y, l.pb.y))

    return true;
    return false;

    }

    bool Intersect(line la, line lb) {

    int c1 = ccw(la.pa, la.pb, lb.pa), c2 = ccw(la.pa, la.pb, lb.pb);

    int c3 = ccw(lb.pa, lb.pb, la.pa), c4 = ccw(lb.pa, lb.pb, la.pb);

    if (c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) {

    if (InLine(la, lb.pa) || InLine(la, lb.pb) || InLine(lb, la.pa) || InLine(lb, la.pb)) return true;
    return false;
    }
    if (c1 * c2 <= 0 && c3 * c4 <= 0) return true;

    return false;

    }
    class SpiralConstruction {
    public:
    vector v;
    point vp[20];
    point p;
    int use[20];
    line l1, l2;
    int maxv;
    void longest(int idx) {
    int i, j;
    int dx, dy;
    if (idx == sz(v)) return ;
    for(i = 0; i < sz(v); i++) {
    if (use[i] == 1) continue;
    if (ccw(vp[idx-1], vp[idx], v[i]) < 0) continue;
    l1.pa = vp[idx]; l1.pb = vp[idx];
    dx = v[i].x - vp[idx].x;
    dy = v[i].y - vp[idx].y;
    while(1) {
    l1.pb.x += dx; l1.pb.y += dy;
    if (l1.pb.x < -1000 || l1.pb.x > 1000 || l1.pb.y < -1000 || l1.pb.y > 1000) break;
    }
    if (ccw(vp[idx-1], vp[idx], v[i]) == 0 && InLine(l1, vp[idx-1])) continue;
    for(j = 1; j < idx; j++) {
    l2.pa = vp[j-1]; l2.pb = vp[j];
    if (Intersect(l1, l2)) break;
    }
    if (j != idx) continue;
    use[i] = 1;
    maxv = max(maxv, idx + 1);
    vp[idx+1] = v[i];
    longest(idx + 1);
    use[i] = 0;
    }
    }
    int longestSpiral(VS points) {
    int i;
    v.clear();
    for(i = 0; i < sz(points); i++) {
    sscanf(points[i].c_str(), "%d %d", &p.x, &p.y);
    v.push_back(p);
    use[i] = 0;
    }
    vp[0].x = 0; vp[0].y = 0;
    maxv = 1;
    for(i = 0; i < sz(v); i++) {
    use[i] = 1;
    vp[1] = v[i];
    longest(1);
    use[i] = 0;
    }
    return maxv;
    }
    };[/code]
    [/spoiler]


    17년 전 link
  • JongMan
    JongMan

    근데 너는 algorithm 도 인클루드했으면서 왜 max min 매크로가 있는거냐 -_-;;


    17년 전 link
  • JongMan
    JongMan

    해당 문제 해설과 소스코드는 http://algospot.com/zbxe/openlecture/2567 를 참조하시면 됩니다. ^^


    17년 전 link
  • JongMan
    JongMan

    다음은 제 소스코드입니다.
    [spoiler="열어보기"]~~~ cpp
    #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;
    int cache[1<<15][16][16];
    struct point
    {
    int y, x;
    point(){}
    point(int y, int x) : y(y), x(x) {}
    };
    struct SpiralConstruction
    {
    int n;
    int left[16][16], right[16][16];
    vector p;
    inline int ccw(const point& a, const point& b, const point& c)
    {
    int x1 = b.x - a.x, y1 = b.y - a.y;
    int x2 = c.x - a.x, y2 = c.y - a.y;
    return x1*y2 - y1*x2;
    }
    int sgn(int x) { return x < 0 ? -1 : (x > 0 ? 1 : 0); }
    bool isValid(int set, int a, int b)
    {
    set &= ~(1< set &= ~(1< if((left[a][b]&set) && (right[a][b]&set)) return false;
    int zero = set&~(left[a][b]|right[a][b]);
    int ys = sgn(p[b].y - p[a].y), xs = sgn(p[b].x - p[a].x);
    REP(i,n) if((zero&(1< return true;
    }
    int go(int points, int a, int b)
    {
    int& ret = cache[points>>1][a][b]; if(ret != -1) return ret;
    ret = 0;
    REP(c,n) if((points&(1<= 0) if(isValid(points, b, c))
    ret >?= go(points | (1< return ret;
    }
    int longestSpiral(vector points)
    {
    n = points.sz;
    if(n <= 2) return n;
    p.pb(point(0,0));
    REP(i,n) { int y, x; sscanf(points[i].c_str(), "%d %d", &x, &y); p.pb(point(y, x)); }

    n = p.sz;
    CLEAR(cache,-1);
    REP(i,n) REP(j,n) if(i != j)
    {
    left[i][j] = right[i][j] = 0;
    REP(k,n)
    {
    int x = ccw(p[i], p[j], p[k]);
    if(x > 0) left[i][j] |= (1< if(x < 0) right[i][j] |= (1< }
    }
    int ret = 0;
    FOR(i,1,n)
    ret >?= go(1+(1<<i), 0, i) + 1;
    return ret;
    }
    };

    Astein 이 올린 에디토리얼과 비슷한 DP 솔루션이고요. ^^ 특이할 만한 것은 left[i][j] 와 right[i][j] 에 i 에서 시작해서 j 를 통과하는 반직선을 기준으로 왼쪽에 있는 점들과 오른쪽에 있는 점들의 비트마스크를 미리 저장해서, 좀 더 validity 를 빠르게 계산하려고 한 것 정도가 되겠네요.
    사실 이것도 느릴 것 같아서 ㅎㄷㄷ 했는데 위에 보니 legend12s 는 백트래킹으로 풀었더라는.. ㅎㄷㄷ[/spoiler]

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