QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106169#6403. Master of PolygondengTL 128ms39024kbJava112.4kb2023-05-16 19:35:262023-05-16 19:35:27

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-16 19:35:27]
  • 评测
  • 测评结果:TL
  • 用时:128ms
  • 内存:39024kb
  • [2023-05-16 19:35:26]
  • 提交

answer


import java.util.Scanner;


public class Main {
  static   class Point{
        double x;
        double y;
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
        public Point() {
        }
    }
    public static void main(String[] args) {

        Scanner scan=new Scanner(System.in);

        int n = scan.nextInt();
        int m = scan.nextInt();
        Point [] p=new Point[n+1];
        for (int i = 1; i <=n; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            p[i]=new Point(x,y);
        }
        p[0]=p[n];
        for (int i = 0; i < m; i++) {
            int x1 = scan.nextInt();
            int y1 = scan.nextInt();
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();

            boolean flag=false;
            for (int j = 1; j <=n; j++) {
                Point a=p[j-1];
                Point b=p[j];
               flag= linesIntersect(a.x, a.y, b.x, b.y, x1, y1, x2, y2);

               if (flag){
                   break;
               }
            }
            if (flag){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }

    public static boolean linesIntersect(double x1, double y1,
                                         double x2, double y2,
                                         double x3, double y3,
                                         double x4, double y4)
    {
        return ((relativeCCW(x1, y1, x2, y2, x3, y3) *
                relativeCCW(x1, y1, x2, y2, x4, y4) <= 0)
                && (relativeCCW(x3, y3, x4, y4, x1, y1) *
                relativeCCW(x3, y3, x4, y4, x2, y2) <= 0));
    }

    public static int relativeCCW(double x1, double y1,
                                  double x2, double y2,
                                  double px, double py)
    {
        x2 -= x1;
        y2 -= y1;
        px -= x1;
        py -= y1;
        double ccw = px * y2 - py * x2;
        if (ccw == 0.0) {
            ccw = px * x2 + py * y2;
            if (ccw > 0.0) {
                px -= x2;
                py -= y2;
                ccw = px * x2 + py * y2;
                if (ccw < 0.0) {
                    ccw = 0.0;
                }
            }
        }
        return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0);
    }


}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 128ms
memory: 39024kb

input:

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2

output:

YES
YES
YES
YES
NO
YES

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: -100
Time Limit Exceeded

input:

20 200000
8838 9219
12190 11292
15953 7581
16690 6159
21104 5484
8978 1076
4354 1065
1261 676
12684 14159
15469 22416
13493 28027
15531 26837
18253 26053
26444 24253
22160 19958
24879 12856
28793 22156
25300 10245
14749 15078
12946 13942
26544 28338 18806 21279
5592 29200 20935 25253
28189 17513 215...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES...

result: