QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#701256 | #8071. Ribbon Road | andahe | WA | 0ms | 3932kb | C++17 | 3.0kb | 2024-11-02 13:58:16 | 2024-11-02 13:58:17 |
Judging History
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: ''