UVa 270 / POJ 1118 Lining Up (计算几何)

2024-03-05 20:32
文章标签 计算 poj 几何 uva 270 1118 lining

本文主要是介绍UVa 270 / POJ 1118 Lining Up (计算几何),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

270 - Lining Up

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=206

http://poj.org/problem?id=1118

``How am I ever going to solve this problem?" said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?

Your program has to be efficient!

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. 
The output consists of one integer representing the largest number of points that all lie on one line.

Sample Input

11 1
2 2
3 3
9 10
10 11

Sample Output

3

思路:

任取一点,计算出其他点到该点斜率后排序,斜率相同的点必然在一条直线上。 
复杂度:O(N^2*log N) 


UVa的代码:

/*0.129s*/#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 1 << 30;char str[20];
double x[705], y[705], d[705];int main(void)
{int t, n, i, j, k;int ans, count;scanf("%d\n", &t);///多读一个换行~while (t--){for (n = 0; gets(str); ++n){if (str[0] == '\0') break;sscanf(str, "%lf%lf", &x[n], &y[n]);}//ans = 1;for (i = 0; i < n - 1; ++i){for (j = i + 1, k = 0; j < n; ++j, ++k)d[k] = (x[j] == x[i] ? INF : (y[j] - y[i]) / (x[j] - x[i]));sort(d, d + k);count = 1;for (j = 1; j < k; ++j){if (fabs(d[j] - d[j - 1]) < 1e-9){++count;ans = max(ans, count);}else count = 1;}}printf("%d\n", ans + 1);if (t) putchar('\n');}return 0;
}


POJ的代码:

/*125ms,204KB*/#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 1 << 30;char str[20];
double x[705], y[705], d[705];int main(void)
{int n, i, j, k;int ans, count;while (scanf("%d", &n), n){for (i = 0; i < n; ++i)scanf("%lf%lf", &x[i], &y[i]);ans = 1;for (i = 0; i < n - 1; ++i){for (j = i + 1, k = 0; j < n; ++j, ++k)d[k] = (x[j] == x[i] ? INF : (y[j] - y[i]) / (x[j] - x[i]));sort(d, d + k);count = 1;for (j = 1; j < k; ++j){if (fabs(d[j] - d[j - 1]) < 1e-9){++count;ans = max(ans, count);}else count = 1;}}printf("%d\n", ans + 1);}return 0;
}

Source

East Central North America 1994

这篇关于UVa 270 / POJ 1118 Lining Up (计算几何)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/777727

相关文章

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直