배치고사 B번 별모양 검사 질문 있습니다.

  • 로제폰
    로제폰

    앞의 글 힌트대로 일단 모든 점을 볼 수 있는 영역을 찾은 후에 영역을 이루는 점들에 대해서 모든 점들을 볼 수 있는지를 체크했습니다. 샘플이랑 몇 개 예제 만든 건 잘 되는데 WA가 뜨네요.
    이런 건 처음 짜보는거라 알고리즘이 잘못되었을 거 같은데 도움 부탁드립니다. 대충 설명하자면 밖에 큰 사각형을 만들고 각 선분에서 폴리곤 안쪽을 향하는 방향쪽으로 사각형을 잘라가면서 영역을 계속 업데이트 하는 방식으로 구했습니다. 끝난 뒤엔 만들어진 영역 각 점에서 폴리곤 각 점으로 선을 그을 때 크로스되는지를 체크했습니다. 아래가 소스입니다.

    #include<stdio.h>
    #include<math.h>
    #include<algorithm>
    #include<memory.h>
    #include<vector>
    using namespace std;
    
    struct Point {
      double x, y;
      Point() {};
      Point(double _x, double _y) {
        x = _x; y = _y;
      }
    };
    
    struct Line {
      Point st, ed;
      double a, b, c;
    
      Line() {}
      Line(Point s, Point e) {
        st = s; ed = e;
        a = ed.y-st.y; 
        b = st.x - ed.x;
        c = -a*st.x-b*st.y;
      }
    };
    
    int isCCW(Point a, Point b, Point c) {
      int temp;
      temp  = a.x*b.y - b.x*a.y;
      temp += b.x*c.y - c.x*b.y;
      temp += c.x*a.y - a.x*c.y;
    
      if(temp > 1e-9) return 1;
      else if(temp < -1e-9) return -1;
      return 0;
    }
    
    bool isOnTheSegment(Point st, Point ed, Point p) {
    #define maxf(x, y) x > y-1e-9 ? x : y
    #define minf(x, y) x < y+1e-9 ? x : y
      Point tSt(minf(st.x, ed.x), minf(st.y, ed.y)), tEd(maxf(st.x, ed.x), maxf(st.y, ed.y));
      if(p.x > tSt.x - 1e-9 && p.x < tEd.x + 1e-9 && p.y > tSt.y - 1e-9 && p.y < tEd.y + 1e-9) {
        if(fabs((ed.y-st.y)*(p.x-st.x) - (ed.x-st.x)*(p.y-st.y)) < 1e-9)
          return true;
      }
      return false;
    }
    
    bool isCross(Point p1, Point p2, Point t1, Point t2, bool checkOnTheSegment) {
      int ppt, ttp;
      ppt = isCCW(p1, p2, t1) * isCCW(p1, p2, t2);
      ttp = isCCW(t1, t2, p1) * isCCW(t1, t2, p2);
    
      if(ppt < 0 && ttp < 0)
        return true;
      else if(checkOnTheSegment)
        return isOnTheSegment(p1, p2, t1) || isOnTheSegment(p1, p2, t2) || isOnTheSegment(t1, t2, p1) || isOnTheSegment(t1, t2, p2);
    
      return false;
    }
    
    Point getCrossPoint(Line a, Line b, bool &is) {
      Point cp;
      if(fabs(a.b*b.a - a.a*b.b) < 1e-9)
        is = false;
      else {
        cp.x = (a.c*b.b - b.c*a.b) / (a.b*b.a - a.a*b.b);
        cp.y = (a.a*b.c - a.c*b.a) / (a.b*b.a - a.a*b.b);
        is = true;
      }
    
      return cp;
    }
    
    int main() {
      freopen("input.in", "r", stdin);
    
      int n;
      while(scanf("%d", &n) == 1 && n != 0) {
        vector<Point> ps;
        for(int i = 0;i<n;i++) {
          Point temp;
          scanf("%lf%lf", &temp.x, &temp.y);
          ps.push_back(temp);
        }
    
        vector<Line> edge;
        Point w[4] = {Point(-101.0, 10003.0), Point(-101.0, -101.0), Point(10003.0, -101.0), Point(10003.0, 10003.0)};
        edge.push_back(Line(w[0], w[1]));
        edge.push_back(Line(w[1], w[2]));
        edge.push_back(Line(w[2], w[3]));
        edge.push_back(Line(w[3], w[0]));
    
        for(int i = 0;i<n;i++) {
          Line l(ps[i], ps[(i+1)%n]);
    
          Point cp[2];
          int idx[2], nCp = 0, onSeg[2] = {0, 0};
          for(int j = 0;j<edge.size() && nCp < 2;j++) {
            bool is;
            Point tcp = getCrossPoint(l, edge[j], is);
            if(is && isOnTheSegment(edge[j].st, edge[j].ed, tcp)) {
              idx[nCp] = j;
              cp[nCp] = tcp;
              if((fabs(tcp.x - edge[j].st.x) < 1e-9 && fabs(tcp.y - edge[j].st.y) < 1e-9)) {
                onSeg[nCp] = 1;
                j++;
              }
              else if(fabs(tcp.x - edge[j].ed.x) < 1e-9 && fabs(tcp.y - edge[j].ed.y) < 1e-9) {
                onSeg[nCp] = 2;
                j++;
              }
              nCp++;
            }
          }
    
          if(nCp != 2)
            continue;
    
          vector<Line> newEdge;
          int nowCCW1 = isCCW(cp[0], cp[1], Point(-101.0, -103.0)), nowCCW2 = isCCW(l.st, l.ed, Point(-101.0, -103.0));
          if(nowCCW1 != nowCCW2) {
            int from = idx[0]+1, to = idx[1]-1;
    
            newEdge.push_back(Line(cp[1], cp[0]));
            if(onSeg[0] == 0)
              newEdge.push_back(Line(cp[0], edge[idx[0]].ed));
            else if(onSeg[0] == 1)
              from = idx[0];
    
            for(int i = from;i<=to;i++)
              newEdge.push_back(edge[i]);
    
            if(onSeg[1] == 0)
              newEdge.push_back(Line(edge[idx[1]].st, cp[1]));
            else if(onSeg[1] == 2)
              to = idx[1];
          }
          else {
            int from = idx[1]+1, to = idx[0]-1;
    
            newEdge.push_back(Line(cp[0], cp[1]));
            if(onSeg[1] == 0)
              newEdge.push_back(Line(cp[1], edge[idx[1]].ed));
            else if(onSeg[1] == 1)
              to = idx[1];
    
            for(int i = from;i<edge.size();i++)
              newEdge.push_back(edge[i]);
            for(int i = 0;i<=to;i++)
              newEdge.push_back(edge[i]);
    
            if(onSeg[0] == 0)
              newEdge.push_back(Line(edge[idx[0]].st, cp[0]));
            else if(onSeg[0] == 2)
              from = idx[0];
          }
    
          edge = newEdge;
        }
    
        vector<Line> polygon;
        for(int i = 0;i<n;i++)
          polygon.push_back(Line(ps[i], ps[(i+1)%n]));
    
        bool isStar = true;
        for(int i = 0;i<edge.size();i++) {
          for(int j = 0;j<n;j++) {
            for(int k = 0;k<polygon.size();k++) {
              if(isCross(edge[i].st, ps[j], polygon[k].st, polygon[k].ed, false)) {
                isStar = false;
                j = n; i = edge.size(); break;
              }
            }
          }
        }
        printf("%d\n", isStar);
      }
    }
    

    13년 전
2개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    우선 코드에 제 강의의 흔적이 보여서 뿌듯하군요. :D
    어쨌든.. 우선 방법 자체를 생각해보면, 모든 선분을 볼 수 있는 영역을 구하셨다면, 그런 영역이 존재하는 순간 Yes가 될 것이고, 영역이 존재하지 않으면 No입니다. 그러니까 영역을 구하셨다면, 그 이후에는 별다른 처리가 필요하지 않은 거죠. 제 방법을 설명하자면, 입력으로 주어진 모든 선분을 직선으로 만들고, 그 n개의 직선으로 만들어지는 모든 교점 n*(n-1)/2 개를 후보로 삼아서, 모든 선분을 볼 수 있느냐를 검사했습니다. 선분을 볼 수 있냐는 선분 교차로 할 수도 있지만, 사실 이거보다 각도를 이용해서 검사하는 게 편합니다. 다만 colinear한 선분이 문제가 되는데, 이 경우를 잘 고려해주면 AC를 받아낼 수 있을 겁니다. :D


    13년 전 link
  • 로제폰
    로제폰

    Taeyoon_Lee //
    저도 그냥 모든 선분을 직선화한 후 모든 교점을 대상으로 ccw체크를 해서 모든 선분을 볼수있는지를 체크해서 풀었습니다. 제가 짠 영역 구하는 코드는 잘못된 것이 있는지 안되네요. 나중에 문제점을 찾아봐야겠습니다. 답변 감사합니다.


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