装修免费咨询平台seo研究中心骗局
2021江苏省赛热身赛 C Magic Rabbit(数形结合)
Magic Rabbit
非常好且巧妙地一道题。
大意：给出三种溶液 ， 三种溶液分别含有不同浓度的 x ，y 两种物质。
| 溶液 | x (mg/ml) | y (mg/ml) |
|---|---|---|
| 溶液1 | x1 | y1 |
| 溶液2 | x2 | y2 |
| 溶液3 | x3 | y3 |
给出 Q 组询问 ， 每次给出一个新的溶液浓度(x4 , y4) ， 问是否能用以上三种溶液混合出当前溶液。
思路：不妨设 溶液 1 ， 2 ， 3 分别取 a , b , c ml
显然可以得到式子
a x 1 + b x 2 + c x 3 a + b + c = x 4 \frac{ax_1+bx_2+cx_3}{a+b+c} = x_4 a+b+cax1+bx2+cx3=x4
a y 1 + b y 2 + c y 3 a + b + c = y 4 \frac{ay_1+by_2+cy_3}{a+b+c} = y_4 a+b+cay1+by2+cy3=y4
问题就变成了求这个方程组是否有解 ， 显然是不好求的。
这时候我们转变思路 ， 先求两种溶液的情况。
a x 1 + b x 2 a + b = x 4 \frac{ax_1+bx_2}{a+b} = x_4 a+bax1+bx2=x4
a y 1 + b y 2 a + b = y 4 \frac{ay_1+by_2}{a+b} = y_4 a+bay1+by2=y4
设
λ = a a + b \lambda = \frac{a}{a+b} λ=a+ba
λ x 1 + ( 1 − λ ) x 2 = x 4 \lambda x_1+(1-\lambda )x_2 = x_4 λx1+(1−λ)x2=x4
λ y 1 + ( 1 − λ ) y 2 = y 4 \lambda y_1+(1-\lambda )y_2 = y_4 λy1+(1−λ)y2=y4
转化成向量组的形式
[ x 2 y 2 ] + λ [ x 1 − x 2 y 1 − y 2 ] = [ x 4 y 4 ] ( 0 ≤ λ ≤ 1 ) \begin{bmatrix} x_2\\y_2 \end{bmatrix} +\lambda \begin{bmatrix} x_1-x_2\\y_1-y_2 \end{bmatrix}=\begin{bmatrix} x_4\\y_4 \end{bmatrix}(0\le \lambda\le 1) [x2y2]+λ[x1−x2y1−y2]=[x4y4](0≤λ≤1)
观察方程的左边 ， 显然是一个直线的点向式的形式 ， 这个式子表明 ， 我们要求的解一定在(x1 , y1) (x2 , y2) 这两个点所形成的线段上(不考虑退化情况)。
那么当加入第三个点之后 ， 显然解一定在三点所形成三角形内部(包含端点) ， 注意退化情况。
#include<bits/stdc++.h>
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(){IOSfor(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);