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

这篇具有很好参考价值的文章主要介绍了2021江苏省赛热身赛 C Magic Rabbit(数形结合)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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]+λ[x1x2y1y2]=[x4y4](0λ1)文章来源地址https://www.toymoban.com/news/detail-697846.html

观察方程的左边 , 显然是一个直线的点向式的形式 , 这个式子表明 , 我们要求的解一定在(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(){

	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);

到了这里,关于2021江苏省赛热身赛 C Magic Rabbit(数形结合)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • windows10上运行magic keyboard和magic mouse

    所有需要的软件和插件都可以在这里寻找到 链接:https://pan.baidu.com/s/1Y8vjRnznqKP7f8dFFrHoGw?pwd=vpsy 提取码:vpsy 你的windows电脑可能自带了蓝牙,那你直接连接键盘鼠标便可。 若你的windows电脑主板上没有蓝牙,你也可以上网买一个蓝牙接收器,他的价格往往在10RMB左右,效果都差

    2024年02月05日
    浏览(26)
  • Rabbit加密算法

    一、引言 随着信息技术的快速发展,数据安全已成为越来越受到重视的领域。加密算法作为保障数据安全的重要技术手段,在通信、存储等领域得到了广泛应用。Rabbit加密算法作为一种新型的加密算法,凭借其简单易懂的原理、高速的运算性能以及良好的安全性,逐渐引起了

    2024年02月04日
    浏览(30)
  • Rabbit MQ详解

    一、什么是RabbitMQ? 答:RabbitMQ简称MQ是 一套实现了高级消息队列协议的开源消息代理软件 ,简单来说就是 一个消息中间件 。是一种程序对程序的通信方法,其服务器也是以高性能、健壮以及可伸缩性出名的Erlang语言编写而成。 二、RabbitMQ是干什么的? 答:RabbitMQ简单来说

    2024年01月16日
    浏览(47)
  • 江苏工匠杯-web

    该题考察序列化反序列化及Linux命令执行相关知识。 首先,代码定义了一个名为ease的类,其中__construct()接收两个参数$method和$args,并将它们赋值给对应的属性。__destruct()在对象销毁时自动调用。它首先检查$method是否在可调用的方法数组中,如果是,则使用call_user_func_array(

    2024年03月25日
    浏览(41)
  • Rabbit health check failed

    说明: 项目并未配置rabbitmq,但是每次项目启动的时候总是会报错,rabbitmq连接异常,健康检查失败,但是不影响项目运行。 具体报错信息如下: 具体查看报错内容后发现: 原来是项目配置了spring健康检查: 解决: 在配置文件中添加rabbitmq的健康检查忽略 再次启动项目,报

    2024年02月11日
    浏览(31)
  • Rabbit MQ使用Linux操作

    2024年02月15日
    浏览(32)
  • Rabbit算法:轻量高效的加密利器

    Rabbit算法是由Martin Boesgaard和Mette Vesterager提出的一种流密码算法,其设计初衷是为了提供高性能和高度安全性的加密方案。Rabbit算法结合了非线性的置换、置换和异或运算,以及密钥调度算法,使其成为一种优秀的加密算法。 Rabbit加密解密 | 一个覆盖广泛主题工具的高效在线

    2024年03月13日
    浏览(50)
  • echarts 3D立体图(江苏版)

    npm install echarts@4.9.0 echarts-gl@1.0.1 --legacy-peer-deps 安装echarts插件和echarts 3D地图插件 配置main.js 新建vue文件 如需改样式点这里 npm install echarts@4.9.0 echarts-gl@1.0.1 --legacy-peer-deps 安装echarts插件和echarts 3D地图插件 配置main.js 新建vue文件 如需改样式点这里

    2024年02月12日
    浏览(39)
  • 江苏图采之证件照上传

            第一步,下载android studio          安装 Android Studio  |  Android 开发者  |  Android Developers (google.cn)         第二步,安装的时候,勾选Android Virtual Device         第三步,进入studio,它会自动安装一些sdk,最好挂梯子,不然容易404         第四步,创

    2024年02月04日
    浏览(31)
  • 江苏各城市电信DNS地址收集

    地市   主用DNS 备用DNS  南京 218.2.135.1 61.147.37.1 苏州 61.177.7.1 221.228.255.1 无锡   221.228.255.1 218.2.135.1 常州  221.228.255.1 218.2.135.1 镇江 218.2.135.1 61.147.37.1 扬州 61.147.37.1 61.177.7.1 南通 61.147.37.1 61.177.7.1 泰州 221.228.255.1 218.2.135.1 徐州 61.147.37.1 61.177.7.1 淮安 61.147.37.1 61.177.7.1 盐城 6

    2024年02月06日
    浏览(250)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包