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

Eureka

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4182    Accepted Submission(s): 1146


Problem Description
Professor Zhang draws $n$ points on the plane, which are conveniently labeled by $1, 2, ..., n$. The $i$-th point is at $(x_i,y_i)$. Professor Zhang wants to know the number of best sets. As the value could be very large, print it modulo $10^9+7$.

A set $P$ ($P$ contains the label of the points) is called best set if and only if there are at least one best pair in $P$. Two numbers $u$ and $v$ $(u, v \in P, u \ne v)$ are called best pair, if for every $w \in P$, $f(u,v) \ge g(u,v,w)$, where $f(u,v)=\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ and $g(u,v,w)=\frac{f(u,v)+f(v,w)+f(w,u)}{2}$.
 

Input
There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ $(1 \le n \le 1000)$ -- then number of points.

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ $(-10^9 \le x_i, y_i \le 10^9)$ -- coordinates of the $i$-th point.
 

Output
For each test case, output an integer denoting the answer.
 

Sample Input
3 3 1 1 1 1 1 1 3 0 0 0 1 1 0 1 0 0
 

Sample Output
4 3 0
 

Author
zimpha
 

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-04-15 23:37:04, Gzip enabled