建设简单网站,网站建设佰金手指科杰二六,龙中龙网站开发,城乡与建设部网站首页2021江苏省赛热身赛 C Magic Rabbit(数形结合)
Magic Rabbit
非常好且巧妙地一道题。
大意#xff1a;给出三种溶液 #xff0c; 三种溶液分别含有不同浓度的 x #xff0c;y 两种物质。
溶液x (mg/ml)y (mg/ml)溶液1x1y1溶液2x2y2溶液3x3y3
给出 Q 组询问 #xff0c…2021江苏省赛热身赛 C Magic Rabbit(数形结合)
Magic Rabbit
非常好且巧妙地一道题。
大意给出三种溶液 三种溶液分别含有不同浓度的 x y 两种物质。
溶液x (mg/ml)y (mg/ml)溶液1x1y1溶液2x2y2溶液3x3y3
给出 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_1bx_2cx_3}{abc} x_4 abcax1bx2cx3x4 a y 1 b y 2 c y 3 a b c y 4 \frac{ay_1by_2cy_3}{abc} y_4 abcay1by2cy3y4
问题就变成了求这个方程组是否有解 显然是不好求的。
这时候我们转变思路 先求两种溶液的情况。 a x 1 b x 2 a b x 4 \frac{ax_1bx_2}{ab} x_4 abax1bx2x4 a y 1 b y 2 a b y 4 \frac{ay_1by_2}{ab} y_4 abay1by2y4
设 λ a a b \lambda \frac{a}{ab} λaba λ x 1 ( 1 − λ ) x 2 x 4 \lambda x_1(1-\lambda )x_2 x_4 λx1(1−λ)x2x4 λ y 1 ( 1 − λ ) y 2 y 4 \lambda y_1(1-\lambda )y_2 y_4 λy1(1−λ)y2y4
转化成向量组的形式 [ 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) 这两个点所形成的线段上(不考虑退化情况)。
那么当加入第三个点之后 显然解一定在三点所形成三角形内部(包含端点) 注意退化情况。
#includebits/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 pairint,intPII;//--------------------------------------------------------------
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);
