P7504 - Kirakira

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：0 通过：0

There are

n stars in the sky. At every moment, the

i-th of them has a probability of

ui/vi(1≤ui<vi<P=31607) to become visible. All stars are independent of each other. The position of a star can be described as a coordinate on a 2D plane. No two stars share the same coordinate. Your task is to compute the expectation value of the area of the convex hull formed by the visible stars.
Formally, let

P=31607. It can be shown that the answer can be expressed as an irreducible fraction

p/q, where

p and

q are integers and

q≢0(modP). Output the integer equal to

p⋅q−1modP. In other words, output such an integer

x that

0≤x<P and

x⋅q≡p(modP).

The first line contains a single integer

1≤T≤100), denoting the number of test cases.
For each test case, the first line contains a single integer

(1≤n≤1000), denoting the number of stars.
Each of the following

nlines describes a stars. The

i-th line of them contains 4 integers

xi,yi,ui,vi(−1000≤xi,yi≤1000,1≤ui<vi<P=31607)indicating the coordinate of the

i-th star and the probability of the

i-th star to become visible. It is guaranteed that no two stars share the same coordinate.
There are at most

3test cases satisfying

n>20.

Output the integer equal to

p⋅q−1modP denoting the answer.

21730
21730

2020 Multi-University Training Contest 6

7504: Kirakira

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签