UVA 270 Lining Up 共线点暴力

开发者广运技术 2022年11月10日

0 收藏 863 点赞 3,159 浏览 1411 个字

题意：给出几个点的位置，问一条直线最多能连过几个点。

只要枚举每两个点组成的直线，然后找直线上的点数，更新最大值即可。

我这样做过于暴力，2.7s让人心惊肉跳。。。应该还能继续剪枝的，同一直线找过之后就可以剪掉了。

代码：

 /*
 *   Author:        illuz <iilluzen@gmail.com>
 *   Blog:          http://blog.csdn.net/hcbbt
 *   File:          uva270.cpp
 *   Lauguage:      C/C++
 *   Create Date:   2013-08-25 10:54:55
 *   Descripton:    UVA 270 Lining Up, greed, enumeration, brute force
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repu(i, a, b) for (int i = (a); i < (b); i++)
#define repf(i, a, b) for (int i = (a); i <= (b); i++)
#define repd(i, a, b) for (int i = (a); i >= (b); i--)
#define swap(a, b) {int t = a; a = b; b = t;}
#define mc(a) memset(a, 0, sizeof(a))
#define ms(a, i) memset(a, i, sizeof(a))
#define sqr(x) ((x) * (x))
#define FI(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
typedef long long LL;
typedef unsigned long long ULL;/****** TEMPLATE ENDS ******/const int MAXN = 710;
int cas, n;
char str[100];
pair<int, int> p[MAXN];int main() {
scanf("%d\n", &cas);
rep(c, cas) {
n = 0;
while (gets(str) && strlen(str)) {
//puts(str);
sscanf(str, "%d%d", &p[n].first, &p[n].second);
n++;
}
int Max = 1, sum;
rep(i, n) repu(j, i + 1, n) {
sum = 2;
int tx = p[i].first - p[j].first, ty = p[i].second - p[j].second;
rep(k, n) {
if (k == i || k == j) continue;
if ((p[k].first - p[i].first) * ty == (p[k].second - p[i].second) * tx)
sum++;
}
if (sum > Max)
Max = sum;
}
if (c) printf("\n");
printf("%d\n", Max);
}
return 0;
}