HDU-6731 Angle Beats 计算几何 直角三角形个数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6731
题意:n个点,m次查询,每次给你一个点,从n个点挑出两个能组成多少直角三角形
题解:假设询问的是点p,直角可能是p也可能是其他两点的某个,当是其他点时,我们枚举n个点,让他作为直角,这样就能确定出一条直线,在直线上的点数就是当前能构成直角三角形的个数,如果在通过枚举的话肯定是不行的,所以我们预处理出每两个点直线方程,k和b,哈希保存下来(这个直接用long double就可以了,之前用的用1e9+7来哈希,但是超时了),然后就可以二分确定下当前的数目,如果直角是p这个点,那么也是相同的处理方法,但是这样得到的数目要除2,因为多算了一半,唉...
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
typedef long long ll;
const ll mod = 2e9 + 7;
const ll jz = 100007;
const int N = 2010;
struct node {ll x, y;
}p[N];
int n, m;
tr1::unordered_map<ll, ll> mp;
vector<long double> v[N];
ll num[N];vector<long double> vp;
ll nump;
/*
ll ksm(ll x, ll y) {
// if(mp[x]) return mp[x];ll res = 1;while(y) {if(y & 1) res = res * x % mod;y >>= 1;x = x * x % mod;}return res;
}
*/
int main() {long double k, b;ll x, y;ll res1, res2;long double cnt;while(~scanf("%d %d", &n, &m)) {for(int i = 1; i <= n; i++) {scanf("%lld %lld", &p[i].x, &p[i].y);v[i].clear();num[i] = 0;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(i == j) continue;if(p[i].x == p[j].x) num[i]++;else {k = (long double)(p[i].y - p[j].y) / (p[i].x - p[j].x);b = p[i].y - k * p[i].x;v[i].push_back(k * mod + b);}}sort(v[i].begin(), v[i].end());}while(m--) {scanf("%lld %lld", &x, &y);res1 = res2 = 0;nump = 0;vp.clear();for(int i = 1; i <= n; i++) {if(y == p[i].y) res1 += num[i];else {k = (long double)(p[i].x - x) / (y - p[i].y);b = p[i].y - k * p[i].x;cnt = k * mod + b;res1 += upper_bound(v[i].begin(), v[i].end(), cnt) - lower_bound(v[i].begin(), v[i].end(), cnt); }if(p[i].x == x) nump++;else {k = (long double)(p[i].y - y) / (p[i].x - x);b = p[i].y - k * p[i].x;cnt = k * mod + b;vp.push_back(cnt);}}sort(vp.begin(), vp.end());// cout << nump << endl;for(int i = 1; i <= n; i++) {if(y == p[i].y) res2 += nump;else {k = (long double)(p[i].x - x) / (y - p[i].y);b = y - k * x;cnt = k * mod + b;res2 += upper_bound(vp.begin(), vp.end(), cnt) - lower_bound(vp.begin(), vp.end(), cnt); }}// cout << res1 << " " << res2 << endl;printf("%lld\n", res1 + res2 / 2);}}return 0;
}
[ Copy to Clipboard ] [ Save to File]
相关文章:

HDU-6731 Angle Beats 计算几何 直角三角形个数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid6731 题意:n个点,m次查询,每次给你一个点,从n个点挑出两个能组成多少直角三角形 题解:假设询问的是点p,直角可能是p也可能是其他两点的某…...

HDU - 5927 Auxiliary Set dfs序+瞎搞
题目链接:https://vjudge.net/problem/HDU-5927 题意:给一棵树,然后每次询问时给出哪些点是不重要的点,让求这棵树上重要的点以及是两个不同的重要的点的lca一共有多少个 题解:我们只需要看给出的每一个不重要的点是不是重要的点就可以了&a…...

CodeForces - 689D Friends and Subsequences ST表+二分
题目链接:https://codeforces.com/problemset/problem/689/D 题意:有多少区间[l, r]满足,max(al..ar) min(bl..br) 题解:对于先固定l,那么对于max(a),是一个递增的序列,对于min(b)是一个递减…...

2017南宁 I. Rake It In dfs博弈
题目链接:https://nanti.jisuanke.com/t/A1538 题解:因为k只有3,所以最多取6次,每次有9种选取可能,所以直接dfs选取即可 #include <bits/stdc.h> using namespace std; typedef long long ll; int b[6][6]; in…...

CodeForces - 369E Valera and Queries 树状数组+离线+容斥思想
题目链接:https://vjudge.net/problem/CodeForces-369E 题意:n条线段,m次询问,给出cnt个点,问这些点在多少线段上 题解:如果每个点对于所在的线段上没有影响的话,那么我们就可以建立权值线段树…...

Gym - 101889I Imperial roads 树链剖分+最小生成树之必选一边
题目链接:https://vjudge.net/problem/Gym-101889I 题意:n个点,m条边,q次询问,每次必须选一边,求最小生成树的权值 题解:我们先跑一边最小生成树,然后按照最小边建树,必…...

CodeForces - 1228C Primes and Multiplication 数贡献
题目链接:https://vjudge.net/problem/CodeForces-1228C 题解:把x的每个质因子找出来,计算n!对每个因子的贡献 #include <bits/stdc.h> using namespace std; typedef long long ll; const ll mod 1e9 7; const int N …...

CodeForces - 1228D Complete Tripartite 图上的哈希
题目链接:https://vjudge.net/problem/CodeForces-1228D 题解:我们把每个点哈希,这样就能计算出和每个点连接的其他点的总哈希值,若只有三种哈希值的和,那么就是符合的,当然还有其他很多种做法。 #includ…...

2017 ICPC Asia Urumqi I. A Possible Tree 带权并查集
题目链接:https://nanti.jisuanke.com/t/40520 题解:因为他们都是联通的且只有唯一路径,所以不用管之前怎么连的,直接按照他给的查询,带权并查集判断即可 #include <bits/stdc.h> using namespace std; const …...

HDU - 5923 Prediction 多个并查集
题目链接:https://vjudge.net/problem/HDU-5923 题解:因为n只有500个,所以我们可以每个点维护一个并查集,所以判断某些点的时候,这些并查集在合起来即可 #include <bits/stdc.h> using namespace std; const int N 510; struct edge…...

2018徐州 Gym - 102028J Carpets Removal 概率事件+二维差分
题目链接:https://vjudge.net/problem/Gym-102028J 题意:去掉两个矩形,让剩下的矩形覆盖的点最少 题解:使剩下的点少,那么我们就是去掉的两个矩形覆盖的尽可能多,也就是两个矩形各自占据的格子和只有两个…...
Gym - 102307J Jail Destruction 线段树
题目链接:https://vjudge.net/problem/Gym-102307J The semester has just begun at Universidad Nacional (UNAL). As usual, a group of vandals enjoys bringing chaos to all students and damaging the university facilities. Those guys have been planning…...

Gym - 101955L Machining Disc Rotors 计算几何 圆剩余部分直径
题目链接:https://vjudge.net/problem/Gym-101955L 题意:n个圆和 圆(0,0,R) 部分相交,求剩余圆的直径 题解:如果剩余部分存在直径的话,那就是2*R,这个怎么判断呢,对于每…...

Gym - 102307E Extreme Image 线段树 扫描线
题目链接:https://vjudge.net/problem/Gym-102307E 题意:平面上n个点,给定区域的w和d范围,求区域最大的点数 题解:其实和在平面上给定长和宽 是一样的道理,这个只需要对角度排序,然后对于每个…...

Gym - 102307C Common Subsequence dp
题目链接:https://vjudge.net/problem/Gym-102307C 题意:两个字符串的匹配长度能不能达到99%; 题解:因为n为1e5,所以不能直接dp[i][j]表示到(i,j)的最长匹配长度了,因为失配的最多1000,因此dp…...

18南京 Gym - 101981M Mediocre String Problem 扩展kmp+马拉车
题目链接:https://vjudge.net/problem/Gym-101981M 题意:求 s的一个子串后面加上t的前缀为回文串并且满足|s| > |t| 的个数 题解:因为牵扯到了前缀和子串的问题,大体就能想到要用到扩展kmp,我们把s倒置࿰…...

CodeForces - 374D Inna and Sequence 线段树
题目连接:https://vjudge.net/problem/CodeForces-374D 题意:n次操作,先给出m个数,原先有一个空序列,每次操作给出一个数,为1或0都放在后面,为-1时,删除m个位置的数 题解ÿ…...

ICPC Asia HongKong 2017
南京已成炮灰,徐州加油! A:java二分 import java.math.*; import java.util.*; public class Main {public static void main(String [] args){Scanner cinnew Scanner(System.in);int t,n;BigInteger z,zn,znjyn,ans,tans,x,XBigInteger.O…...

1225 D. Power Products 哈希
题目链接:http://codeforces.com/problemset/problem/1225/D 题意:有多少种组合方式,使得两个数相乘 能写成 x^k 的形式 题解:首先x^k,x的每个素因子的数目都是k的倍数,那么我们就对于每个数的素因子个数…...

1080 F. Katya and Segments Sets 主席树
题目链接:https://codeforces.com/contest/1080/problem/F 题意:有k个线段所属在n个集合中,每次询问a b x y,问是否[a, b]的每个集合中都存在一个线段在[x, y]的范围内 题解:按照每个线段的有区间排序,然…...

Kattis - largesttriangle Largest Triangle 平面最大三角形面积
题目链接:https://vjudge.net/problem/Kattis-largesttriangle 题意:任意三点的最大三角形面积 题解:首先想到最大的面积应该出现在凸包上,然后就是枚举任意两点,能想到第三点是满足线性的,所以第三点线性…...

数据挖掘-k平均算法
/* 题目内容:实现k平均算法的代码,并且通过样例 代码: */ #include <bits/stdc.h> using namespace std; #define eps 1e-8 #define INF 0x3f3f3f3f const int N 1e6 10; int n, k; pair<double, double> a[N], b[N]; vector&l…...

初识matlab
简单的数学运算: 极限运算: limit(f,x,x0): 计算x→x0时函数f的极限。 举例: syms x y1(1x2*sin(x))^(2/x); y2((1x)^0.5-2)/(x^2-2*x-3); y3x^2*sin(1/x)/sqrt(2*x^2-1); f1limit(y1,0) f2limit(y2,3) f3limit(y3,inf…...

MATLAB学习知识整理 从入门到放弃
简介: Matlab: 美国MathWorks公司出品的商业数学软件。是一种高级技术计算语言和交互式环境。 主要用于: 算法开发 数据可视化 数据分析 数值计算 一、初识matlab 二、matlab数组运算与…...

matlab数组运算与数组化编程
matlab中的运算和操作主要是以数组为对象的, 数组又包括:数值数组、字符数组、元胞数组等。 一、数值数组的建立: 1. 直接输入法: 逗号:用来分开数组中的行元素。(可用空格代替) 分号&#…...

matlab程序设计
一、自定义函数 格式:函数句柄 (自变量列表)函数表达式 例1 定义函数,并计算f(x)在点x-2,1,2.5,3,5.2的值。 f(x)x.^23*x5 x[-2,1,2.5,3,5.2] y1f(x) 二、 m-文件函数(子程序) 格式:function [y1,y2]ff(x1,x…...

matlab数值计算
第一节 多项式运算 一、多项式的表示、求值、求根 1. 表示: matlab中把多项式表达成一个行向量,该向量中的元素是按多项式降幂排列的。 p[2,3,-1,4,5]表示多项式: 显示多项式的数学形式: p1poly2str(p,x) 如&…...

matlab图形功能
//...

python实现键盘输入多个值
Python 2里面读取输入的函数是raw_input(), Python 3的是input(),读入一个值后回车读取输入就退出了,想要一次读取多个输入,可以像下面这样: a, b raw_input().split()1 2a Out[224]: 1b Out[225]: 2 上面保存的是字…...

VS2019在win10下配置boost库
第一步:官网下下载:https://www.boost.org/users/history/version_1_73_0.html win10选择boost_1_73_0.zip 第二步:解压 第三步:编译 打开VS命令行 选择 已压缩好的boost_1_73_0文件夹 运行 bootstrap.bat 成功之后运行 刚…...

pthread_cond_wait()
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); 该函数第一个参数为条件变量指针,第二个为互斥量指针。该函数调用前,需本线程加锁互斥量,加锁状态的时间内函数完成线程加入等待队列操作 ,线程进入等待前…...

pthread多线程学习
基于pthread学习 多线程编程...
线程私有数据
线程私有数据实现的主要思想是:在分配线程私有数据之前,创建与该数据相关联的健,这个键可以被进程中的所有线程使用,但每个线程把这个键与不同的线程私有数据地址进行关联,需要说明的是每个系统支持有限数量的线程特定…...

创建线程的几种方式
class A {int x; public:void f(int x, char c) { };int operator()(int N) { return 0; } }; void foo(int x){} int main() {A a;thread t1(a, 6); // 传递a的拷贝给子线程thread t2(ref(a), 6); //传递a的引用给子线程thread t3(move(a), 6); //a在主线程中将不再有效threa…...

c++11多线程学习
一.join和detach C中的thread对象通常来说表达了执行的线程(thread of execution),这是一个操作系统或者平台的概念。 当thread::join()函数被调用后,调用它的线程会被block,直到线程的执行被完成。基本上࿰…...

Socket编程
C Socket 编程:https://blog.csdn.net/sinat_35866463/article/details/81019778 windows环境下用c实现socket编程:https://blog.csdn.net/xiaoquantouer/article/details/58001960 win7系统两台电脑之间利用Socket实现文件传输---C实现:ht…...

inet_pton()和inet_ntop()函数
https://blog.csdn.net/zyy617532750/article/details/58595700 1.把ip地址转化为用于网络传输的二进制数值 int inet_aton(const char *cp, struct in_addr *inp); inet_aton() 转换网络主机地址ip(如192.168.1.10)为二进制数值,并存储在struct in_addr结构中&a…...
C/C++内存泄漏及检测
“该死系统存在内存泄漏问题”,项目中由于各方面因素,总是有人抱怨存在内存泄漏,系统长时间运行之后,可用内存越来越少,甚至导致了某些服务失败。内存泄漏是最难发现的常见错误之一,因为除非用完内存或调用…...

八大设计模式原则
1.依赖倒置原则 高层模块不依赖底层模块,二者都应该依赖抽象 抽象不依赖实现细节,实现细节应该依赖于抽象 这一原则与下面的针对接口编程而不是针对实现编程是一个道理,我们设计一个程序,我们应该先想好我们想要抽象什么&#x…...

C++设计模式
管理变化, 提高复用 两种手段:分解 抽象 八大原则:https://blog.csdn.net/mmk27_word/article/details/108521903 重构技法: 静态 -> 动态 早绑定 -> 晚绑定 继承 -> 组合 编译时依赖 -> 运行时依赖 紧耦合 ->…...

LRU算法
#include <iostream> #include <list> #include <map> using namespace std; class LRU {struct node {int key, val;node(int k_ 0, int v_ 0) {key k_;val v_;}};public:int cap; // 大小map<int, list<node>::iterator> mp;list<node&…...
数据库事务四个特性
ACID特性 数据库管理系统中事务(transaction)的四个特性(分析时根据首字母缩写依次解释):原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性…...
Git入门简介
本文简单介绍一下Git的使用,主要内容有下: Git基本介绍Git相较于SVN的优势Git使用流程及常用命令 Git基本介绍 Git是一款免费、开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目 —— [ 百度百科 ] GitHub:https…...

《移动App测试实战》读书笔记
总的来讲,这本书基本涵盖了移动App测试的方方面面,并结合各个专题做了简单讲解,对于扩展无线端测试的知识面有极大的好处,缺点是知识点点到为止,毕竟全书300多页的篇幅也不可能对知识点进行专题讲解。书中作者提到的一…...

http load介绍
前几天工作中要对项目的接口做简单压测,就使用了http load做了简单测试,下面介绍一下这款工具的使用说明。简介:http_load是基于linux平台的性能测试工具,它体积非常小,仅100KB。它以并行复用的方式运行,可…...
工具介绍:ITerm 2
今天介绍一款终端工具ITerm2,有了它,大大提供了我们的工作效率;官方地址:http://www.iterm2.com/ 颜控首选,不多说,上图: bg图片、字体、颜色等都可以在Preferences里设置,强大&…...

shell编写图片抓取器
最近在看《Linux Shell脚本攻略》一书,书中有个图片抓取器的script,抓取出来记录一下。适用范围:适合抓取html里符合img标签正则规则的图片。 #!/bin/bash if [ $# -ne 3 ] thenecho "Usage: $0 URL -d DIRECTORY"exit -1 fi for …...

SSH免密码登录
公司服务器很多的话,如果每次连接都需要输入密码,那就太麻烦了。So,免密登录就可以大大提高我们的工作效率了。 下面介绍ssh免密登录的方法: 实现步骤: 1.在你的自己的机器下面使用ssh-keygen命令来实现创建公钥 使…...
Jmeter访问HTTPS请求
公司最近在搞全站HTTPS改造,进一步提高网站的安全性,防止运营商劫持。那么,改造完成后,所有前后端的URL将全部为https。 So ,研究下怎么用Jmeter访问https请求呢。 其实很简单, 第一步在jmeter中创建HTT…...

《Maven实战》读书笔记
之前对Maven有些认识,通过这本书《Maven实战》一起系统的回顾一下,总结的东西不会很全面,但都是日常工作中最常用的。 简介: maven翻译为“知识的积累”,基于项目对象模型(Project Object Model࿰…...