Codeforces 851B/C
B. Arpa and an exam about geometry
传送门:http://codeforces.com/contest/851/problem/B
本题是一个平面几何问题。
平面上有3个点A,B,C,坐标分别为(ax,ay),(bx,by),(cx,cy)。现以平面上一点P为中心,将点A,B,C旋转角度θ,旋转后的点分别为A’,B’,C’。试问:是否存在点P和角度θ,使得“点A’与点B重合,点B’与点C重合”?
以上条件等价于:存在点P和角度θ,使得“|PA|=|PB|=|PC|,且∠APB=∠BPC=θ”。
考虑点A,B,C的几何关系:
若A,B,C位于同一条直线上,则不存在满足条件的点P和角度θ;
若A,B,C不位于同一条直线上,若存在满足条件的点P和角度θ,则由等价条件可知:△APB≌△BPC,因此|AB|=|BC|。
因此,题中条件成立,当且仅当“A,B,C不共线,且|AB|=|BC|”。
A,B,C三点共线的一个充分条件是直线AB与BC的斜率相等,但这是一个充分不必要条件。
A,B,C三点共线的一个充分必要条件可以通过向量形式给出:
向量α1=(Δx1,Δy1)T,α2=(Δx2,Δy2)T,其中Δx1=bx-ax,Δy1=by-ay,Δx2=cx-bx,Δy2=cy-by。
若向量α1与α2共线,则向量组α1,α2线性相关。设A=(α1,α2),则detA=0。
$$\det A=\left|\begin{matrix}\Delta x_1&\Delta x_2\\\Delta y_1&\Delta y_2\end{matrix}\right|=0\Leftrightarrow\Delta x_1\cdot\Delta y_2=\Delta x_2\cdot\Delta y_1$$
因此,A,B,C三点共线的一个充分必要条件是Δx1·Δy2=Δx2·Δy1。参考程序如下:
#include <stdio.h>
#include <stdint.h> int main(void)
{
int ax, ay, bx, by, cx, cy;
scanf("%d%d%d%d%d%d", &ax, &ay, &bx, &by, &cx, &cy);
int64_t dx1 = bx - ax, dy1 = by - ay;
int64_t dx2 = cx - bx, dy2 = cy - by;
if (dx1 * dy2 == dx2 * dy1) printf("No\n");
else {
if (dx1 * dx1 + dy1 * dy1 == dx2 * dx2 + dy2 * dy2) printf("Yes\n");
else printf("No\n");
}
return ;
}
C. Five Dimensional Points
传送门:http://codeforces.com/contest/851/problem/C
本题是一个空间几何问题。
在五维空间中,有n个不同的点P1,P2,...,Pn,Pi的坐标为(ai,bi,ci,di,ei)。现有定义:点A为bad,当且仅当存在不同于点A的点B和点C,使得向量AB与AC的夹角为锐角;否则,点A为good。求{1,2,...,n}的子集S,使得对于S中的每一个元素i,均有Pi为good。
向量的夹角按照以下公式计算:$<\boldsymbol{a},\boldsymbol{b}>=\arccos \frac{\boldsymbol{a}\cdot \boldsymbol{b}}{|\boldsymbol{a}||\boldsymbol{b}|}$
而对于向量a=(a1,a2,...,ak),b=(b1,b2,...,bk),内积a·b的计算公式为: $\boldsymbol{a}\cdot\boldsymbol{b}=\sum_{j=1}^{k}{a_{j}b_{j}}$
本题直接模拟即可,时间复杂度为O(n3)。
参考程序如下:
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 1000 typedef int quint[]; quint p[MAX_N], v[MAX_N][MAX_N];
int good[MAX_N]; int main(void)
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) {
for (int k = ; k < ; k++) {
scanf("%d", &p[i][k]);
}
}
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
for (int k = ; k < ; k++) {
v[i][j][k] = p[j][k] - p[i][k];
}
}
}
int cnt = ;
for (int t = ; t < n; t++) {
bool flag = false;
for (int i = ; i < n; i++) {
for (int j = ; j < i; j++) {
int inp = ;
for (int k = ; k < ; k++) {
inp += v[t][i][k] * v[t][j][k];
}
if (inp > ) {
flag = true;
break;
}
}
}
if (!flag) {
good[cnt++] = t + ;
}
}
printf("%d\n", cnt);
for (int i = ; i < cnt; i++) {
printf("%d\n", good[i]);
}
return ;
}
最新文章
- 几种常见语言的命名空间(Namespace)特性
- POJ3308 Paratroopers(最小割/二分图最小点权覆盖)
- 转:CentOS设置时区
- 基于Elasticsearch的自定义评分算法扩展
- PE制作实录 —— 定义我的 PE 工具箱
- BZOJ3280: 小R的烦恼
- wpf Content数据绑定StringFormat起作用的原理和解决(转)
- [ES6] Array -- Destructuring and Rest Parameters &;&; for ..of &;&; Arrat.find()
- Python作用域
- OC--初始化UINavigationController
- 基于 Vue 全家桶制作的移动端音乐 WebApp
- ASP.NET Core 运行原理剖析
- Codeforces Round #425 (Div. 2)C
- MVC Controller return 格式分类及用法
- Atitit 翻页功能的解决方案与版本历史 v4 r49
- HDU 1873 看病要排队 优先队列
- [原]linux下将网卡设置为混杂模式
- php array 根据value获取key,in_array()判断是否在数组内实例
- “unauthorized: authentication required” -- openshift3.9 docker push 报错
- NGINX 如何防盗链