QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106176#6403. Master of PolygondengTL 2ms3632kbC++142.0kb2023-05-16 19:49:492023-05-16 19:49:50

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:49:50]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3632kb
  • [2023-05-16 19:49:49]
  • 提交

answer

#include <stdlib.h>
#include <math.h>
#include <bits/stdc++.h>
#define MAXN 1000
using namespace std;
const double eps=1e-8;
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;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	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;
}



详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3632kb

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: