QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106175 | #6403. Master of Polygon | deng | TL | 3ms | 3496kb | C++14 | 1.9kb | 2023-05-16 19:49:20 | 2023-05-16 19:49:21 |
Judging History
answer
#include <stdlib.h>
#include <math.h>
#include <bits/stdc++.h>
#define MAXN 200001
using namespace std;
const double eps=1e-10;
struct Point{
double x,y;
Point(){}
Point(int x,int y):x(x),y(y){}
Point operator -(Point B){
return Point(x-B.x,y-B.y);
}
};
Point P[MAXN];
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);
}
bool 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));
}
int main(){
int n,m;
cin >> n >> m;
for(int i = 1 ; i <=n ; i ++){
Point p;
cin >> p.x >> p.y;
P[i] = p;
}
Point p;
p.x=P[n].x;
p.y=P[n].y;
P[0]=p;
for(int i = 1 ; i <=m ; i ++){
Point p1,p2;
cin >> p1.x >> p1.y>> p2.x >> p2.y;
bool 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,p1.x,p1.y,p2.x,p2.y);
if(flag){
break;
}
}
if(flag){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3496kb
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...