poj 2780 Linearity 【高效版 同一条直线上的点】

2023-11-05 05:08

本文主要是介绍poj 2780 Linearity 【高效版 同一条直线上的点】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题才真的没有那么的水,可能因为测试数据很多,然后又每个数据有1000个点要处理,用O(n^3)的三重循环直接TLE掉了。。。

所以得另想办法,后来参考了一下别人的想法,得用极角排序,一个sort()就可以了,极角为0的因为无法做分母,所以得单独考虑,终于AC。。。


AC的代码:

#include <stdio.h>
#include <iostream>
#include <algorithm>using namespace std;int x[1002],y[1002];int main()
{int n;int i,j,k,max;while(scanf("%d",&n)!=EOF){//输入for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);max=2;//每次循环都判断for(k=1;k<=n;k++){int count1=1;double angle[1002];int zero=0;for(i=1;i<=n;i++){//单独处理分母为0的情况if(x[i]-x[k]==0)zero++;elseangle[count1++]=(double)(y[i]-y[k])/(double)(x[i]-x[k]);}//按极角的大小进行排序sort(&angle[1],&angle[count1]);//看排序的里面有几个连续的数int temp=2;int sum=2;double pos=angle[1];for(i=2;i<count1;i++){//是相同的就count++if(pos==angle[i])sum++;//否则就重头开始计数else{pos=angle[i];if(sum>temp)	temp=sum;	sum=2;}}if(temp>max)   max=temp;if(zero>max)   max=zero;}printf("%d\n",max);}return 0;
}



TLE的代码:

#include <stdio.h>int x[1002],y[1002];int main()
{int n;while(scanf("%d",&n)!=EOF){int i;//输入坐标点的值for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);//暴搜开始int count,max=-1;int j,k;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++){count=2;for(k=j+1;k<=n;k++)if((y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])) count++;if(max<count) max=count;}printf("%d\n",max);}return 0;
}


这篇关于poj 2780 Linearity 【高效版 同一条直线上的点】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/347607

相关文章

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》:本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE

Tomcat高效部署与性能优化方式

《Tomcat高效部署与性能优化方式》本文介绍了如何高效部署Tomcat并进行性能优化,以确保Web应用的稳定运行和高效响应,高效部署包括环境准备、安装Tomcat、配置Tomcat、部署应用和启动T... 目录Tomcat高效部署与性能优化一、引言二、Tomcat高效部署三、Tomcat性能优化总结Tom

Python利用自带模块实现屏幕像素高效操作

《Python利用自带模块实现屏幕像素高效操作》这篇文章主要为大家详细介绍了Python如何利用自带模块实现屏幕像素高效操作,文中的示例代码讲解详,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、获取屏幕放缩比例2、获取屏幕指定坐标处像素颜色3、一个简单的使用案例4、总结1、获取屏幕放缩比例from

使用Python实现高效的端口扫描器

《使用Python实现高效的端口扫描器》在网络安全领域,端口扫描是一项基本而重要的技能,通过端口扫描,可以发现目标主机上开放的服务和端口,这对于安全评估、渗透测试等有着不可忽视的作用,本文将介绍如何使... 目录1. 端口扫描的基本原理2. 使用python实现端口扫描2.1 安装必要的库2.2 编写端口扫

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》:本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI