2021江苏省赛热身赛 C Magic Rabbit(数形结合)

2021江苏省赛热身赛 C Magic Rabbit(数形结合)

Magic Rabbit

非常好且巧妙地一道题。

大意：给出三种溶液 ， 三种溶液分别含有不同浓度的 x ，y 两种物质。

给出 Q 组询问 ， 每次给出一个新的溶液浓度(x4 , y4) ， 问是否能用以上三种溶液混合出当前溶液。

思路：不妨设 溶液 1 ， 2 ， 3 分别取 a , b , c ml

显然可以得到式子

$$\frac{a{x}_1+b{x}_2+c{x}_3}{a+b+c}=x_4$$

$$\frac{a{y}_1+b{y}_2+c{y}_3}{a+b+c}=y_4$$

问题就变成了求这个方程组是否有解 ， 显然是不好求的。

这时候我们转变思路 ， 先求两种溶液的情况。

$$\frac{a{x}_1+b{x}_2}{a+b}=x_4$$

$$\frac{a{y}_1+b{y}_2}{a+b}=y_4$$

设

$$\lambda =\frac{a}{a+b}$$

$$\lambda x_1+(1-\lambda )x_2=x_4$$

$$\lambda y_1+(1-\lambda )y_2=y_4$$

转化成向量组的形式

[ x 2 y 2 ] + λ [ x 1 − x 2 y 1 − y 2 ] = [ x 4 y 4 ] ( 0 ≤ λ ≤ 1 )

+\lambda =(0\le \lambda\le 1) [x2​y2​​]+λ[x1​−x2​y1​−y2​​]=[x4​y4​​](0≤λ≤1)

观察方程的左边 ， 显然是一个直线的点向式的形式 ， 这个式子表明 ， 我们要求的解一定在(x1 , y1) (x2 , y2) 这两个点所形成的线段上(不考虑退化情况)。

那么当加入第三个点之后 ， 显然解一定在三点所形成三角形内部(包含端点) ， 注意退化情况。

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

//--------------------------------------------------------------
const double eps = 1e-5;
const double pi = acos(-1);
inline double sqr(double x) {return x * x;} //平方
int sign(double x){
	if(fabs(x) < eps) return 0;
	if(x > 0) return 1;
	return -1;
}//符号
struct point{
	double x , y;
	point(){}
	point(double a , double b) : x(a) , y(b){}
	friend point operator + (const point &a , const point &b){
		return point(a.x + b.x , a.y + b.y);
	}
	friend point operator - (const point &a , const point &b){
		return point(a.x - b.x , a.y - b.y);
	}
	friend bool operator == (const point &a , const point &b){
		return !sign(a.x - b.x) && !sign(a.y - b.y);
	}
	friend point operator * (const point &a , const double &b){
		return point(a.x * b , a.y * b);
	}
	friend point operator * (const double &a , const point &b){
		return point(a * b.x , a * b.y);
	}
	friend point operator / (const point &a , const double &b){
		return point(a.x / b , a.y / b);
	}
	//向量模长 
	double norm(){ 
		return sqrt(sqr(x) + sqr(y));
	}
}; 

double det(const point &a , const point &b){
	return a.x * b.y - a.y * b.x;
}//叉积 判断两点共线 

double dot(const point &a , const point &b){
	return a.x * b.x + a.y * b.y;
}//点积

double dist(const point &a , const point &b){
	return (a - b).norm();
}//两点距离
 
point rotate_point(const point &a , const point &p , double A){
	double tx = p.x - a.x , ty = p.y - a.y;
	return point(a.x + tx * cos(A) - ty * sin(A) , a.y + tx * sin(A) + ty * cos(A));
}// p 点 绕 a 点逆时针旋转 A 弧度

int toleft(const point &p , const point &a , const point &b) {
	return sign(det(b - a , p - a));
	// 1 左 0 上 -1 右
}//只适用凸多边形

//判断点 p 是否在线段 st 上(包括端点)
bool point_on_segment(point p , point s , point t){
	return sign(det(p - s , t - s)) == 0 && sign(dot(p - s , p - t)) <= 0;
}

//判断两线段是否相交 ab cd
bool segment_intersect(const point &a , const point &b , const point &c , const point &d){
	//先判断 三点共线 或 四点共线
	if(point_on_segment(a , c , d) || point_on_segment(b , c , d) || point_on_segment(c , a , b) || point_on_segment(d , a , b)) return 1;
	if(sign(toleft(a , c , d)) * sign(toleft(b , c , d)) < 0 && sign(toleft(c , a , b)) * sign(toleft(d , a , b)) < 0) return 1;
	return 0;
}

//--------------------------------------------------------------

point p[4] , now;
double x , y;
int n;
signed main(){

	IOS
	for(int i = 1 ; i <= 3 ; i ++){
		cin >> x >> y;
		p[i] = point{x , y};
	}
	cin >> n;
	
	int tag = -1;
	
	if(p[1] == p[2] && p[2] == p[3]) tag = 0;
	else if(point_on_segment(p[1] , p[2] , p[3])) tag = 1;
	else if(point_on_segment(p[2] , p[1] , p[3])) tag = 2;
	else if(point_on_segment(p[3] , p[1] , p[2])) tag = 3;
	else tag = 4;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> x >> y;
		now = {x , y};
		if(tag == 0){
			if(now == p[1]) cout << "YES\n";
			else cout << "NO\n";
		}
		if(tag == 1){
			if(point_on_segment(now , p[2] , p[3])) cout << "YES\n";
			else cout << "NO\n";
		}
		if(tag == 2){
			if(point_on_segment(now , p[1] , p[3])) cout << "YES\n";
			else cout << "NO\n";
		}
		if(tag == 3){
			if(point_on_segment(now , p[2] , p[1])) cout << "YES\n";
			else cout << "NO\n";
		}
		if(tag == 4){
			bool f = 0;
			if(point_on_segment(now , p[2] , p[3]) || point_on_segment(now , p[1] , p[3]) || point_on_segment(now , p[2] , p[1])) f = 1;
			if(toleft(now , p[2] , p[3]) > 0 && toleft(now , p[3] , p[1]) > 0 && toleft(now , p[1] , p[2]) > 0) f = 1;
			if(toleft(now , p[2] , p[3]) < 0 && toleft(now , p[3] , p[1]) < 0 && toleft(now , p[1] , p[2]) < 0) f = 1;
			if(f) cout << "YES\n";
			else cout << "NO\n";
		}
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137