90分QwQ
  • 板块P1142 轰炸
  • 楼主ilE4Ri9dx
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/4/24 21:16
  • 上次更新2023/10/28 02:57:31
查看原帖
90分QwQ
655467
ilE4Ri9dx楼主2022/4/24 21:16

1个TLE,求神犇优化
(不会题解里的向量用斜率做的)

#include<bits/stdc++.h>
#define N 710
#define inf 0x7f7f7f7f
using namespace std;
int n,ans=0;
struct Node{
	int x,y;
}node[N];
double get_slope(int x1,int y1,int x2,int y2){
	double ret;
	if(x1==x2) ret=inf;
	else ret=(1.0*y1-1.0*y2)/(1.0*x1-1.0*x2);
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&node[i].x,&node[i].y);
	}
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			int x1,y1,x2,y2,tmp=2;
			x1=node[i].x;
			y1=node[i].y;
			x2=node[j].x;
			y2=node[j].y;
			double slope=get_slope(x1,y1,x2,y2);
			if(slope==inf){
				for(int k=1;k<=n;k++){
					if(k==i||k==j) continue;
					int x3,y3;
					x3=node[k].x;
					y3=node[k].y;
					if(x3==x2) tmp++;
				}
			}else{
				for(int k=1;k<=n;k++){
					if(k==i||k==j) continue;
					int x3,y3;
					x3=node[k].x;
					y3=node[k].y;
					double slope2=get_slope(x2,y2,x3,y3);
					if(slope2!=slope) continue;
					else tmp++;
				}
			}
			ans=max(ans,tmp);
		}
	}
	printf("%d",ans);
	return 0;
}
2022/4/24 21:16
加载中...