洛谷 P1142 轰炸
题目描述
“我该怎么办？”飞行员klux向你求助。
事实上，klux面对的是一个很简单的问题，但是他实在太菜了。
klux要想轰炸某个区域内的一些地方，它们是位于平面上的一些点，但是（显然地）klux遇到了抵抗，所以klux只能飞一次，而且由于飞机比较破，一点起飞就只能沿直线飞行，无法转弯。现在他想一次轰炸最多的地方。
输入输出格式
输入格式：
第一行为n
输入数据由n对整数组成(1<=n<=700)，每对整数表示一个点的坐标。没有一个点会出现两次。
输出格式：
一个整数，表示一条直线能覆盖的最多的点数。
输入输出样例
输入样例#1：
5
1 1
2 2
3 3
9 10
10 11
输出样例#1：
3
说明
本题翻译并改编自uva270，数据及解答由uva提供。
题解：
主要就是暴力枚举和判断两点是否在同一条直线上啊；
找到公式就好了。
(x[zzz]-x[z])*(y[zzz]-y[zz])==(y[zzz]-y[z])*(x[zzz]-x[zz])
90分，TLE了一个点。
#include<cstdio>
int max(int x,int y)
{
return x>y?x:y;
}
int x[],y[];
bool check(int z,int zz,int zzz)
{
return (x[zzz]-x[z])*(y[zzz]-y[zz])==(y[zzz]-y[z])*(x[zzz]-x[zz])?true:false;
}
int n,ans,answer=;
int main()
{
scanf("%d",&n);
for(int i=; i<=n; i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=; i<n; i++)
{
for(int j=i+; j<=n; j++)
{
ans=;
for(int k=; k<=n; k++)
{
if(k==i||k==j) continue;
if(check(i,j,k)) ans++;
}
answer=max(answer,ans);
}
}
printf("%d",answer);
return ;
}
/*
5
1 1
2 2
3 3
9 10
10 11 3
*/
过去的代码风格
#include<cstdio>
int max(int x,int y) {
return x>y?x:y;
}
int x[],y[];
bool check(int z,int zz,int zzz) {
return (x[zzz]-x[z])*(y[zzz]-y[zz])==(y[zzz]-y[z])*(x[zzz]-x[zz])?true:false;
}
int n,ans,answer=;
int main() {
scanf("%d",&n);
for(int i=; i<=n; i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=; i<n; i++) {
for(int j=i+; j<=n; j++) {
ans=;
for(int k=; k<=n; k++) {
if(k==i||k==j) continue;
if(check(i,j,k)) ans++;
}
answer=max(answer,ans);
}
}
printf("%d",answer);
return ;
}
/*
5
1 1
2 2
3 3
9 10
10 11 3
*/
现在的代码风格
然后，不用函数，并且输出改成cout，就A了，，，
学长好像讲过，cout输出数字比printf快
#include<cstdio>
#include<iostream>
int max(int x,int y) {
return x>y?x:y;
}
int x[],y[];
int n,ans,answer=;
int main() {
scanf("%d",&n);
for(int i=; i<=n; i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=; i<n; i++) {
for(int j=i+; j<=n; j++) {
ans=;
for(int k=; k<=n; k++) {
if(k==i||k==j) continue;
if((x[k]-x[i])*(y[k]-y[j])==(y[k]-y[i])*(x[k]-x[j])) ans++;
}
answer=max(answer,ans);
}
}
std::cout<<answer;
return ;
}
依旧是现在的代码风格
一世安宁