本文主要是介绍[LightOJ 1292] Laser Shot (几何,判断共线),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LightOJ - 1292
刚开始写的时候是O( n3log(n) )的,枚举两个点,得到一条直线,用set记录下来,然后再 O( n )地计数,居然没有卡过 orz
听了学长的教导,get到一个几何常用思路,正确解法如下
枚举一个点,再枚举其他点,计算到这个点的斜率,make_pair(dx,dy)塞到map里,把相同斜率的计数一下
这样时间复杂度为 O(
#if _WIN32||_WIN64
#define lld I64d
#define llu I64u
#endif
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}int N;
int inpt[710][2];map <pair<int,int>,int> Map;int main()
{int T;scanf("%d", &T);for(int ck=1; ck<=T; ck++){scanf("%d", &N);for(int i=1; i<=N; i++){scanf("%d%d", &inpt[i][0], &inpt[i][1]);}int ans=0;for(int i=1; i<=N; i++){Map.clear();for(int j=1; j<=N; j++){if(i==j) continue;int dx=inpt[i][0]-inpt[j][0],dy=inpt[i][1]-inpt[j][1];if(dx<0) {dx=-dx;dy=-dy;}int G=GCD(dx,dy);dx/=G;dy/=G;Map[make_pair(dx,dy)]++;ans=maxx(Map[make_pair(dx,dy)],ans);}}printf("Case %d: %d\n", ck, ans+1);}return 0;
}
这篇关于[LightOJ 1292] Laser Shot (几何,判断共线)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!