B. Tell Your World(几何数学 + 思维)
1 second
256 megabytes
standard input
standard output
Connect the countless points with lines, till we reach the faraway yonder.
There are n points on a coordinate plane, the i-th of which being (i, yi).
Determine whether it's possible to draw two parallel and non-overlapping lines, such that every point in the set lies on exactly one of them, and each of them passes through at least one point in the set.
The first line of input contains a positive integer n (3 ≤ n ≤ 1 000) — the number of points.
The second line contains n space-separated integers y1, y2, ..., yn ( - 109 ≤ yi ≤ 109) — the vertical coordinates of each point.
Output "Yes" (without quotes) if it's possible to fulfill the requirements, and "No" otherwise.
You can print each letter in any case (upper or lower).
5
7 5 8 6 9
Yes
5
-1 -2 0 0 -5
No
5
5 4 3 2 1
No
5
1000000000 0 0 0 0
Yes
In the first example, there are five points: (1, 7), (2, 5), (3, 8), (4, 6) and (5, 9). It's possible to draw a line that passes through points 1, 3, 5, and another one that passes through points 2, 4 and is parallel to the first one.
In the second example, while it's possible to draw two lines that cover all points, they cannot be made parallel.
In the third example, it's impossible to satisfy both requirements at the same time.
算法:几何数学 + 思维
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f
const int maxn = 1e5+; ll a[maxn];
int n; int solve(double k) {
int pos = -;
for(int i = ; i <= n; i++) {
if(a[i] - a[] == (i - ) * k ) {
continue;
}
if(pos == -) {
pos = i; //确定一个新的基点
} else if(a[i] - a[pos] != (i - pos) * k){
return ;
}
}
return pos != -; //判断是否是所有的点都在一条直线上
} int main() {
while(~scanf("%d", &n)) {
for(int i = ; i <= n; i++) {
cin >> a[i];
}
//以三点来确定三条直线,有以下三种情况
double k1 = a[] - a[];
double k2 = 1.0 * (a[] - a[]) / ;
double k3 = a[] - a[];
if(solve(k1) || solve(k2) || solve(k3)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return ;
}
最新文章
- 基于Spring AOP的JDK动态代理和CGLIB代理
- SQLite关系型数据库
- python查找并删除相同文件-UNIQ File-wxPython-v6
- Android.mk
- springmvc+json
- zoj 3620 Escape Time II
- 使用apktool解包和打包apk
- python作业day3修改配置文件
- R语言和数据分析十大:购物篮分析
- Docker镜像的实现原理
- IDEA创建完整目录maven项目
- word20161226
- 【Docker】-NO.131.Docker.1 -【Docker】
- mysql5.5大数据量下表结构升级
- git reset命令使用
- PHP中常用的数组函数总结
- 移动端input 无法获取焦点的问题
- DWZ中刷新dialog的方案解决
- Mininet安装
- hadoop程序MapReduce之average