【计算几何】Magic Rabbit

题意：

有两种元素A和B，和三种不同元素比例的药水，问对于给定的X和Y，能不能利用这三种药水配出元素比例为X：Y的药水
药水可以无限取用

思路：

第一眼看上去以为是个背包或者数学(((遁
后来发现所有能被配出的比例都是这三种药水所围成的三角形之中，从而转化成计算几何问题：如何判断一个点与一个三角形的位置关系

原本我理解的判断位置关系：凸多边形逆时针存储各顶点，然后to-left检测n次
但是题目给定的三个比例并不能一定满足逆时针顺序，进而发现，如果顺时针的话就是to-right，总之点对于所有的直线的关系都一致
Warning:注意退化的情况

不精确的感性证明：

首先先试图举反例，假设这两种元素分别为盐和糖，如果我想要的水比最咸的水还要咸的话显然不能调配出来
接着证明在三角形边上的一定内配出来：众所周知，水多了加面，面多了加水
最后证明三角形内部的一定能配出来：转化成一个点和它的对边...

code:

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
struct Point{
	int x,y;
};
struct Triangle{
	Point p[3];
}Tr;
int to_left(Point a,Point b,Point c){
	Point X={b.x-a.x,b.y-a.y},Y={c.x-a.x,c.y-a.y};
	int ans=X.x*Y.y-X.y*Y.x;//差积
    if(abs(ans)<eps)return 0;//在直线上
    else if(ans>0)return 1;//在直线左侧
    return -1;//在直线右侧
}
signed main(){
	for(int i=0;i<3;i++){
		cin>>Tr.p[i].x>>Tr.p[i].y;
	}
	int n;
	cin>>n;
	Point pt;
	while(n--){
		cin>>pt.x>>pt.y;
		int f1=0,f2=0,f=0;
		for(int i=0;i<3;i++){
			int res=to_left(Tr.p[i],Tr.p[(i+1)%3],pt);
			if(res==1)f1++;
			else if(res==-1)f2++;
			else{
				if(pt.x>=min(Tr.p[i].x,Tr.p[(i+1)%3].x) && pt.x<=max(Tr.p[i].x,Tr.p[(i+1)%3].x) && pt.y>=min(Tr.p[i].y,Tr.p[(i+1)%3].y) && pt.y<=max(Tr.p[i].y,Tr.p[(i+1)%3].y)){
					f=1;
                }
			}
		}
		if(f1==3 || f2==3 || f==1)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}