Parallel Lines(Aizu 1379)
程序员文章站
2022-07-07 18:56:53
...
题意:给出一些点,这些点两两相连成一条直线,问最多能连成多少条直线。
思路:暴力出奇迹!!记得当时比赛做这道题的时候一直依赖于板子,结果却限制了自己的思路,这得改。dfs直接暴力,但是需要将已经走过的点标记一下,用一个循环跳过已经标记的点减少dfs次数,不然得不出正确的结果,因为会出现如下的连线结果(左图),而正确的连线方式应该如右图。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define MIN(a,b) a<b ? a : b
#define MAX(a,b) a>b ? a : b//确实要比C++自带的max函数要快
#define FRE() freopen("in.txt","r",stdin)
using namespace std;
const int maxn = 20;
const int MOD = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> P;
struct Point {
int x,y;
} p[maxn];
struct Line {
int x,y;
} l[maxn];
int m,ans,cnt,vis[maxn];
int upDate() {//遍历任意两条边之间是否平行,更新最大的结果
int res = 0;
for(int i = 0; i<cnt; i++)
for(int j = i+1; j<cnt; j++) {
if(l[i].x*l[j].y == l[i].y*l[j].x){//注意有斜率不存在情况,所以要对等式做一下变形
res++;
}
}
return res;
}
void dfs(int now) {
while(vis[now])//减少dfs次数,同样也是避免出现之前说的情况
now++;
if(now == m) {
ans = MAX(upDate(),ans);
return;
}
vis[now] = 1;
for(int i = 0; i<m; i++) {
if(!vis[i] && cnt != i) {
l[cnt].x = p[now].x - p[i].x;
l[cnt].y = p[now].y - p[i].y;
vis[i] = 1;
cnt++;
dfs(now+1);//枚举的是每种连接方式下的点的个数
cnt--;
vis[i] = 0;
}
}
vis[now] = 0;
return;
}
int main() {
memset(vis,0,sizeof(vis));
scanf("%d",&m);
for(int i = 0; i<m; i++) {
scanf("%d%d",&p[i].x,&p[i].y);
}
ans = 0;
cnt = 0;
dfs(0);
printf("%d\n",ans);
return 0;
}
上一篇: Parallel Lines
下一篇: Android 开发命名规范