F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Angle Beats

Time Limit: 20000/15000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3277    Accepted Submission(s): 583


Problem Description
Given n points $P_1$, $P_2$, .... , $P_n$ on 2D plane and q queries. In i-th query, a point $A_i$ is given, and you should determine the number of tuples (u, v) that 1 $\leq$ u < v $\leq$ n and $A_i$ , $P_u$, $P_v$ form a non-degenerate right-angled triangle.
 

Input
The first line contains two positive integers n, q (2 ≤ n ≤ 2 000, 1 ≤ q ≤ 2 000), denoting the numberof given points and the number of queries.
Next n lines each contains two integers xi , yi (|xi|, |yi| ≤ $10^9$), denoting a given point Pi.
Next q lines each contains two integers xi , yi (|xi|, |yi| ≤ $10^9$), denoting a query point Ai.
It is guaranteed that the input n + q points are all pairwise distinct.
 

Output
Output q lines each contains a non-negative integer, denoting the answer to corresponding query.
 

Sample Input
4 2 0 1 1 0 0 -1 -1 0 0 0 1 1
 

Sample Output
4 3
 

Hint

For query (0, 0), the 4 right-angled triangles are
&#65533; {(0, 0),(0, 1),(1, 0)}
&#65533; {(0, 0),(0, 1),(-1, 0)}
&#65533; {(0, 0),(0,-1),(1, 0)}
&#65533; {(0, 0),(0,-1),(-1, 0)}
For query (1, 1), the 3 right-angled triangles are
&#65533; {(1, 1),(0, 1),(1, 0)}
&#65533; {(1, 1),(0, 1),(0,-1)}
&#65533; {(1, 1),(1, 0),(-1, 0)}
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 13:45:25, Gzip enabled