QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106169 | #6403. Master of Polygon | deng | TL | 128ms | 39024kb | Java11 | 2.4kb | 2023-05-16 19:35:26 | 2023-05-16 19:35:27 |
Judging History
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...