QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#701256#8071. Ribbon RoadandaheWA 0ms3932kbC++173.0kb2024-11-02 13:58:162024-11-02 13:58:17

Judging History

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

  • [2024-11-02 13:58:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3932kb
  • [2024-11-02 13:58:16]
  • 提交

answer

#include<bits/stdc++.h> 
#define ll long long 
#define LL __int128_t 
#define PB push_back 
#define debug(x) cout<<#x<<" "<<x<<endl 
using namespace std;
const int N(100005);
const double EPS=1e-9;
inline int sgn(double a){ return a < -EPS ? -1 : a > EPS; }
inline int cmp(double a, double b){ return sgn(a-b); }
struct Point;
typedef Point Vector;
struct Point{
    double x,y;
    Point(){}
    Point(double a, double b):x(a),y(b){}
    double len(){return sqrt(x*x+y*y);}
    bool onSegment(Point s, Point e);
    int inPolygon(Point poly[]);
    void read() { cin>>x>>y; }
    void out() {cout<<"x: "<<x<<" y: "<<y<<endl;}
    Point operator+(Vector v) {return {x+v.x,y+v.y};}
    Vector operator-(Point p) {return {x-p.x,y-p.y};}
    double operator^(Vector v) {return x*v.y-y*v.x;}//叉乘
    double operator*(Vector v) {return x*v.x+y*v.y;}//点乘
}poly[N];
bool Point::onSegment(Point s, Point e){
	Vector v1 = s-*this;
	Vector v2 = e-*this;
	return sgn(v1^v2)==0&&sgn(v1*v2)<=0;
}
bool onLine(Point x, Point s, Point e){
	Vector v1 = s-x;
	Vector v2 = e-x;
	return sgn(v1^v2)==0;
}
int n;
int Point::inPolygon(Point poly[])
{//判断点是否在多边形内,若点在多边形内返回1,在多边形外部返回0,在多边形上返回-1
    int wn = 0;
    for(int i = 1; i <= n; ++i){
        if((*this).onSegment(poly[i], poly[i%n+1])) return -1;
        int k = sgn((poly[i%n+1] - poly[i])^(*this - poly[i]));
        int d1 = sgn(poly[i].y - y);
        int d2 = sgn(poly[i%n+1].y - y);
        if(k > 0 && d1 <= 0 && d2 > 0) wn++;
        if(k < 0 && d2 <= 0 && d1 > 0) wn++;
    }
    return wn%2;
}
int L[2], p;
int main() 
{ 
	//freopen("1.in","r",stdin); 
	ios::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; ++i) poly[i].read();
	Point ant, line; ant.read(), line.read();
	for(int i = 1; i <= n; ++i)
		if(ant.onSegment(poly[i], poly[i%n+1]))
		{
			Point cp = ant;
			ant.x = (poly[i].x+poly[i%n+1].x)/2;
			ant.y = (poly[i].y+poly[i%n+1].y)/2;
			if(onLine(line, poly[i], poly[i%n+1])) { cout<<"?"<<endl; return 0; }
			Point dec = poly[i%n+1]-poly[i];
			double adx, ady;
			if(!sgn(dec.y)) adx = 0, ady = 1;
			else adx = dec.y, ady = -dec.x;
			Point bsx(ant.x+adx, ant.y+ady);
			Vector base = bsx-ant;
			if(base*(line-ant) < 0) bsx.x -= adx*2, bsx.y -= ady*2, base = bsx-ant;
			for(int j = 1; j <= n; ++j) if(j != i)
			{
				Vector JGbase = ant-poly[j];
				Vector v1 = bsx-poly[j];
				Vector v2 = poly[j%n+1]-poly[j];
				if(sgn(JGbase^v1) != sgn(JGbase^v2) && sgn(JGbase^v2) != 0 && sgn(JGbase^v1)) continue;
				Vector v3 = poly[j] - ant;
				Vector v4 = poly[j%n+1] - ant;
				int d1 = sgn(base^v3);
				int d2 = sgn(base^v4);
				if(d1 >= 0 && d2 < 0) L[p]++;
				else if(d2 >= 0 && d1 < 0) L[p]++;
			}
			ant = cp;
			p++;
		}
	if(p == 2 && (L[0]%2)^(L[1]%2)) cout<<"?"<<endl;
	else if(L[0]%2) cout<<"inside"<<endl;
	else if(!L[0]%2) cout<<"outside"<<endl;
	return 0; 
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3916kb

input:

4
0 0
2 0
2 2
0 2
1 0 1 1

output:

inside

result:

ok single line: 'inside'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

4
0 0
0 2
2 2
2 0
1 0 -1 0

output:

?

result:

ok single line: '?'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4
0 0
5 0
5 5
0 5
4 0 1 0

output:

?

result:

ok single line: '?'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

4
0 0
2 0
2 2
0 2
0 0 1 1

output:

inside

result:

ok single line: 'inside'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

4
0 0
2 0
2 2
0 2
0 0 -1 -1

output:

outside

result:

ok single line: 'outside'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

4
0 0
1 0
1 1
0 1
0 0 1 -1

output:

?

result:

ok single line: '?'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 3 4

output:

?

result:

ok single line: '?'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 2 5

output:

?

result:

ok single line: '?'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 3 5

output:

?

result:

ok single line: '?'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 1 5

output:

outside

result:

ok single line: 'outside'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 2 3

output:

?

result:

ok single line: '?'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 3 3

output:

inside

result:

ok single line: 'inside'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 1 3

output:

?

result:

ok single line: '?'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 4 1 4

output:

?

result:

ok single line: '?'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
1 4 3 3

output:

inside

result:

ok single line: 'inside'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
5 4 3 3

output:

outside

result:

ok single line: 'outside'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 5 3 3

output:

inside

result:

ok single line: 'inside'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

10
0 4
2 4
2 6
6 6
6 4
4 4
4 2
2 2
2 0
0 0
2 1 3 3

output:

outside

result:

ok single line: 'outside'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3
-1000000 -1000000
1000000 999999
2 -4
-499999 -500002 999999 999988

output:

inside

result:

ok single line: 'inside'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

3
-1000000 -1000000
1000000 999999
2 -4
-499999 -500002 999999 999987

output:

outside

result:

ok single line: 'outside'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

3
-701377 132392
760304 132392
760304 780416
-700168 132928 -1000000 0

output:

?

result:

ok single line: '?'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

3
0 0
4 4
2 8
3 6 4 4

output:

?

result:

ok single line: '?'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

3
0 0
4 4
2 8
3 6 2 8

output:

?

result:

ok single line: '?'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

18
1 0
-1 0
-1 1
0 2
0 3
-1 4
0 5
-1 6
0 7
-1 8
0 9
0 10
1 11
1 12
0 13
1 14
0 15
10 16
0 0 0 8

output:

inside

result:

ok single line: 'inside'

Test #25:

score: -100
Wrong Answer
time: 0ms
memory: 3920kb

input:

19
1 0
-1 0
-1 1
0 2
0 3
-1 4
0 5
-1 6
0 7
-1 8
0 9
0 10
1 11
1 12
0 13
1 14
0 15
0 16
-100 -100
0 0 0 8

output:


result:

wrong answer 1st lines differ - expected: 'outside', found: ''