站外题求调
  • 板块灌水区
  • 楼主djwj323
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/6/7 15:17
  • 上次更新2023/10/27 23:48:21
查看原帖
站外题求调
212320
djwj323楼主2022/6/7 15:17

输入一个多边形,每次询问给出一个点,在多边形外输出0,多边形上输出1,多边形内输出2

#include<bits/stdc++.h>
using namespace std;
#define double long double
const double eps=0.0000000001;
class point{
	public:
		double x,y;
		point(double x=0,double y=0):x(x),y(y){}
		point operator +(point _){return point(x+_.x,y+_.y);}
		point operator -(point _){return point(x-_.x,y-_.y);}
		point operator *(double _){return point(x*_,y*_);}
		point operator /(double _){return point(x/_,y/_);}
		double norm(){return x*x+y*y;}
		double ABS(){return sqrt(norm());}
		bool operator <(const point &_)const{return x==_.x?y<_.y:x<_.x;}
		bool operator ==(const point &_)const{return fabs(x-_.x)<=eps&&fabs(y-_.y)<=eps;}
};
typedef point vec;
struct seg{point A,B;};
double dot(point A,point B){return A.x*B.x+A.y*B.y;}
double cross(point A,point B){return A.x*B.y-A.y*B.x;}
//------------------------------------------------------------------------------
point a[103],p;
long long n,q,sum,i;
//------------------------------------------------------------------------------
void work(){
	sum=0;
	for(long long i=1;i<=n;i++){
		if(a[(i%n)+1].y==a[i].y){
			if(p.y==a[i].y&&min(a[(i%n)+1].x,a[i].x)<=p.x&&p.x<=max(a[(i%n)+1].x,a[i].x))  return puts("1"),void();
			continue;
		}
		if(p.y<min(a[i].y,a[(i%n)+1].y)||max(a[i].y,a[(i%n)+1].y)<p.y)  continue;
		double c=(a[(i%n)+1].x-a[i].x)*(p.y-a[i].y)/(a[(i%n)+1].y-a[i].y)+a[i].x;
		if(p.x<c&&p.y!=a[(i%n)+1].y)  sum++;
		else if(p.x==c)  return puts("1"),void();
	}
	if(sum%2==1)  puts("2");
	else  puts("0");
}
int main(){
	for(scanf("%lld",&n),i=1;i<=n;i++)  scanf("%Lf%Lf",&a[i].x,&a[i].y);
	for(scanf("%lld",&q),i=1;i<=q;i++)  scanf("%Lf%Lf",&p.x,&p.y),work();
    return 0;
}
//YuKai AK CSP2022
//YuKai AK NOIP2022
//YuKai AK NOI2022
//YuKai AK IOI2022
//YuKai AK ZJOI2022
2022/6/7 15:17
加载中...