C++(g++ 7.5.0) 解法, 执行用时: 538ms, 内存消耗: 548K, 提交时间: 2023-07-23 19:08:09

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct P{
    ll x,y;
    void in(){cin>>x>>y;}
    P operator+(const P&a)const{return {a.x+x,a.y+y};}
    P operator-(const P&a)const{return {x-a.x,y-a.y};}
    ll operator^(const P&a)const{return x*a.y-y*a.x;}
    ll operator*(const P&a)const{return x*a.x+y*a.y;}
    int lef(const P&a)const{
        const ll v=(*this)^a;
        return (v>0)-(v<0);
    }
}po[N],q;
int n;
struct L{
    P p,v;
    int lef(const P&a)const{return v.lef(a-p);}
};
pair<bool,int>chk(P a){
    int cnt=0;
    for(int i=1;i<=n;i++){
        const P u=po[i],v=po[i%n+1];
        if(!(v-u).lef(a-u)&&(v-a)*(u-a)<=0)return {1,0};
        if(v.y==u.y)continue;
        const L uv={u,v-u};
        if(u.y<v.y&&uv.lef(a)<=0||u.y>v.y&&uv.lef(a)>=0)continue;
        if(u.y<a.y&&v.y>=a.y)cnt++;
        if(u.y>=a.y&&v.y<a.y)cnt--;
    }
    return {0,cnt};
}
signed main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)po[i].in();
    int m;cin>>m;
    while(m--){
        q.in();
        auto[f,c]=chk(q);
        if(f){
            cout<<"EDGE\n";
        }else{
            cout<<c<<'\n';
        }
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 388ms, 内存消耗: 712K, 提交时间: 2022-08-04 16:37:18

#include<iostream>
using namespace std;

struct Po
{
	long long x,y;
}a[5000];

Po operator-(Po a,Po b)
{
	return Po{a.x-b.x,a.y-b.y};
}

long long operator^(Po a,Po b)
{
	return a.x*b.y-b.x*a.y;
}

int Tol(Po a,Po b,Po c)
{
	long long temp=(b-a)^(c-a);
	if(temp>0)return 1;
	else if(temp<0)return -1;
	else return 0;
}

bool Cont(Po a,Po b,Po c)
{
	long long temp=(b-a)^(c-a);
	if(!temp)if(min(a.x,b.x)<=c.x&&max(a.x,b.x)>=c.x)return 1;
	return 0;
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y;
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		Po c;
		cin>>c.x>>c.y;
		Po d;
		d.x=c.x+1;
		d.y=c.y;
		int ok=0;
		int ans=0;
		for(int j=0;j<n;j++)
		{
			if(Cont(a[j],a[(j+1)%n],c))
			{
				cout<<"EDGE\n";
				ok=1;
				break;
			}
			int t1=Tol(c,d,a[j]),t2=Tol(c,d,a[(j+1)%n]),t3=Tol(a[j],a[(j+1)%n],c);
			if(t1>=0&&t2<0&&t3<0)ans--;
			else if(t1<0&&t2>=0&&t3>0)ans++;
		}
		if(!ok)cout<<ans<<"\n";
	}
	return 0;
}