首页 > 其他分享 >AtCoder Beginner Contest 251 G Intersection of Polygons

AtCoder Beginner Contest 251 G Intersection of Polygons

时间:2023-06-16 10:44:37浏览次数:61  
标签:AtCoder typedef Beginner Contest ll long maxn Intersection

洛谷传送门

AtCoder 传送门

经典结论,一个点 \(P(x, y)\) 在一个凸多边形内部 \(S = \{(x_i, y_i)\}\) 的充要条件是 \(\forall i \in [1, n], (x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x - x_i, y - y_i) \ge 0\),其中 \(S\) 的点按照逆时针排列。

然后我们运用叉积的一个性质 \((x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x - x_i, y - y_i) = (x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x, y) - (x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x_i, y_i)\) 就做完了,预处理后项最大值即可。

code
// Problem: G - Intersection of Polygons
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n, m, q, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], f[maxn], g[maxn];

inline ll calc(ll a, ll b, ll c, ll d) {
	return a * d - b * c;
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &a[i], &b[i]);
	}
	scanf("%lld", &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%lld%lld", &c[i], &d[i]);
	}
	a[n + 1] = a[1];
	b[n + 1] = b[1];
	scanf("%lld", &q);
	for (int i = 1; i <= n; ++i) {
		e[i] = a[i + 1] - a[i];
		f[i] = b[i + 1] - b[i];
		g[i] = -9e18;
		for (int j = 1; j <= m; ++j) {
			g[i] = max(g[i], calc(e[i], f[i], a[i] + c[j], b[i] + d[j]));
		}
	}
	while (q--) {
		ll x, y;
		scanf("%lld%lld", &x, &y);
		bool flag = 1;
		for (int i = 1; i <= n; ++i) {
			if (calc(e[i], f[i], x, y) < g[i]) {
				flag = 0;
				break;
			}
		}
		puts(flag ? "Yes" : "No");
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,Beginner,Contest,ll,long,maxn,Intersection
From: https://www.cnblogs.com/zltzlt-blog/p/17484983.html

相关文章

  • AtCoder Beginner Contest 220 G Isosceles Trapezium
    洛谷传送门AtCoder传送门简单题。首先肯定是要枚举梯形其中一条底边的两个端点的。那么另一条底边除了斜率与这条边相等,两个端点的距离要分别与这条底边两个端点的距离相等。发现这个十分不好做,考虑一个梯形是等腰梯形的一个充要条件。不难想到,连接两底中点,这条线段垂直于两......
  • AtCoder Beginner Contest 249 G Xor Cards
    洛谷传送门AtCoder传送门好题。套路地,考虑枚举最优解的\(a\)异或和二进制下与\(k\)的\(\text{LCP}\),设在第\(i\)位不同。这样的好处是\(i\)之后的位可以随便选。之后按位贪心确定最优解\(b\)的异或和。考虑之前的答案是\(res\),当前在确定第\(j\)位,如何判断\(r......
  • AtCoder Beginner Contest 305 题解 A - F
    A-WaterStation题目大意找到离给定的数最近的一个\(5\)的倍数输出即可。解题思路我们取这个数对\(5\)的上下界,也就是整数除以\(5\)再乘以\(5\),以及这个数再加上一个\(5\),比较这两数和给定数的距离即可。ACCode#include<iostream>#include<algorithm>#includ......
  • AtCoder Beginner Contest 219 H Candles
    洛谷传送门AtCoder传送门套路化了。比较显然的关路灯型区间dp。考虑你\(t\)时刻熄灭一个初始长度为\(a\)的蜡烛,得分是\(\max(a-t,0)\),所以尝试把时间塞进状态。设\(f_{i,j,k,0/1}\)表示,熄灭完区间\([i,j]\)的蜡烛,当前时间是\(t\),在左端点还是右端点的最大得......
  • AtCoder Beginner Contest 223 H Xor Query
    洛谷传送门AtCoder传送门考虑一个无脑做法:线段树维护区间线性基。时间复杂度是\(O(m\logn\log^2V)\),过于优秀以至于无法接受。事实上我们并不需要维护区间线性基,因为不带修。考虑“可持久化线性基”,开\(n\)个线性基,第\(i\)个维护前缀\([1,i]\)的数。并且插入线性......
  • AtCoder Beginner Contest 215 H Cabbage Master
    洛谷传送门AtCoder传送门考虑第一问。发现这个东西长得很像二分图匹配,考虑建图,第\(i\)个盒子建\(b_i\)个左部点,第\(i\)个球建\(a_i\)个右部点,每个盒子的每个点往可以放的球的每个点连边。显然要求能被满足等价于,这个二分图存在一个左部点的完全匹配。因为一个盒子的......
  • AtCoder Regular Contest 141 C Bracket and Permutation
    洛谷传送门AtCoder传送门考虑给出\(S\),如何求\(P,Q\)。先考虑\(P\),那我们肯定想让\(P\)的每一项都尽量往前靠。设\([1,k]\)为合法括号串,\(S_{k+1}=\texttt{)}\),那\(P\)的前\(k\)项依次为\(1\simk\),第\(k+1\)项不能为\(k+1\)了,那找到\(k+1\)之......
  • AtCoder Beginner Contest 273(E)
    AtCoderBeginnerContest273(E)E(链式结构,思维)E题目大意就是原本有一个空的序列,我们后面会进行\(q\)次操作,每次操作我们都需要输出此时的序列的最后数字下面有几种操作\(ADD\)\(x\),代表在这在这个序列的最后面添加一个\(x\)\(DELETE\),代表如果此时的序列存在数字的话,......
  • AtCoder Beginner Contest 265 F Manhattan Cafe
    洛谷传送门AtCoder传送门考虑dp,\(f_{i,j,k}\)表示考虑到第\(i\)维,\(\sum\limits_{x=1}^i|p_x-r_x|=j,\sum\limits_{x=1}^i|q_x-r_x|=k\)的方案数。转移是容易的,枚举\(r_i\)即可,\(f_{i,j,k}=\sum\limits_rf_{i-1,j-|p_i-r|,k-|q_i-r|}......
  • Atcoder Beginner Contest 301
    A-OverallWinner题目大意A和T两人玩游戏,给定一串只由A和T组成的字符串,如果第i个字符是A,则A赢得第i轮的胜利,反之则T赢;当遍历完整个字符串后,谁赢的轮数多谁就是最终赢家,如果一样则谁最先达到该轮数谁赢,输出赢家的名字解题思路签到题不多嗦了神秘代码......