POJ 1118 求平面上最多x点共线
2024-08-31 03:47:59
题意:给你n个点的坐标。求一条直线最多能穿过多少个点。
思路:枚举(n^2)+求斜率+排序 (复杂度n^2logn)大功告成
//By: Sirius_Ren
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,maxx;double s[705];
struct line{int x,y;}a[705];
bool cmp(line a,line b){return a.x<b.x;}
int main()
{
while(scanf("%d",&n)&&n){
maxx=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+1+n,cmp);
for(int i=1;i<n;i++){
int tot=1,ans=0;
for(int j=i+1;j<=n;j++)
s[tot++]=(1.0*a[j].y-1.0*a[i].y)/(1.0*a[j].x-1.0*a[i].x);
sort(s+1,s+tot);
for(int i=1;i<tot-1;i++)
if(fabs(s[i+1]-s[i])<1e-6)ans++,maxx=max(maxx,ans);
else ans=0;
}
printf("%d\n",maxx+2);
}
}
最新文章
- java之DatagramSocket、DatagramPackage丶MulticastSocket 广播学习
- Testing - Tips
- When using SqlDependency without providing an options value, SqlDependency.Start() must be called prior to execution of a command added to the SqlDependency instance.
- 看好你的门-客户端传数据-用java修改referer
- c语言知识点
- 在Hdsi2.0 SQL的注入部分抓包分析语句
- c# partial类
- 剑指Offer:面试题8——旋转数组的最小值(java实现)
- 自定义弧形的 tabBar
- SQL Server 格式化时间format
- SDUT 2893-B(DP || 记忆化搜索)
- Java编程中时区和时间相关的问题
- 朱晔和你聊Spring系列S1E2:SpringBoot并不神秘
- OpenRASP安装使用教程
- 15:IO之File、Properties类
- Vue.js常用指令:v-bind
- 如何让docker以daemon方式运行/bin/bash
- 推荐系统之隐语义模型(LFM)
- swagger配置
- 【Java nio】 NonBlocking NIO
热门文章
- vsftpd:500OOPS:vsftpd:refusingtorunwithwritablerootinsidechroot()错误的解决方法
- vue 打印 页面特定部分转pdf
- S-HR之OSF
- HDU 3152 Obstacle Course(优先队列,广搜)
- c/c++排坑(3) -- c/c++中的switch语句
- 使用Python的Flask框架,结合Highchart,动态渲染图表
- 找零钱的算法实现(Java)
- python BeautiulSoup
- Codeforces 918C/917A - The Monster
- asp.net--mvc--异步编程