24h購物| | PChome| 登入
2013-06-26 14:26:00| 人氣469| 回應0 | 上一篇 | 下一篇

[UVA] 11004 - Changing Roadmap

推薦 0 收藏 0 轉貼0 訂閱站台

Problem A
Changing Roadmap
Input: Standard Input

Output: Standard Output

 

Like many other cities Texas is now facing trouble with excessive traffic flow and hence traffic Jam. That is why the Governor of Texas is planning to build many new roads. The roads of Texas can be considered as straight lines, and they are in general position, which means that no two roads are parallel and no three roads are concurrent. Roads are denoted by three integers a, b, c, which actually denotes a road with equation the ax+by+c=0 in a two dimensional Cartesian coordinate system. New roads will be build in Texas according to the following plan:

 

a)     The city authority has identified PP very important places. These places can be considered as points in a two dimensional Cartesian coordinate system. New roads will be built from all the existing junctions (where two roads intersect) to all the important places. So JJ*PP new roads will be built, where JJ is the number of junctions. So all these new roads will be straight-line segments, each of them connecting one junction and one very important place.

b)     Suppose the equation of the i-th and j-th road (j>i) is aix+biy+ci=0 and ajx+bjy+cj=0. Then the roads connecting the junction of these two roads and any important place will be of the form aix+biy+ci+k(ajx+bjy+cj)=0. If k is positive, then the road is built by Positive Builders Ltd, and if k is negative then the road is built by Negative Builders Ltd.

 

Figure: A typical roadmap with four roads, two important places and six junctions. So the number of new roads to be built is 2*6=12

 

Given the equation of N existing roads of Texas, your job is to find out how many of the roads will be built by the Negative Builders Ltd.              

 

Input

The input file contains at most 12 sets of inputs. The description of each set is given below:

 

Each set starts with an integer N (0<N<=3000), which denotes the number of existing roads in Texas. Each of the next N lines contains three integers ai, bi, ci (1 ≤ i ≤ N and –10000 ≤ ai , bi, ci ≤ 10000), which actually denotes that the i-th street has an equation aix + biy + ci = 0. The next line contains an integer PP (1 ≤ P ≤ 100), which indicates the number of very important places. Each of the next PP lines contains two integers xi, yi that indicates the coordinates of the i-th important place is (xi, yi). No important places will be on the existing roads.

 

Input is terminated by a block whose first line contains a zero.

 

Output

For each set of input produce two lines of output. The first line contains the serial of the roadmap and the second line reports how many of new roads, will be built by the Negative Builders Ltd. Look at the output for sample input for the exact format.

 

Sample Input                 Output for Sample Input

5
-3954 -4700 5677
7190 -5953 3085
-3903 -2020 -7990
-4618 618 -4421
4162 3918 8248
3
3 7
-5 7
-5 -8
6
7697 3593 -4874
3311 2882 -5983
2871 1429 -6858
9436 -8954 -4656
9294 6173 5035
-3924 1911 3733
3
5 -8
1 -10
4 -7
0

Roadmap 1:

Negative Builders Ltd. will build 16 New Roads.

Roadmap 2:

Negative Builders Ltd. will build 23 New Roads.

 


Problem setter: Shahriar Manzoor, EPS

Special Thanks: Derek Kisman, EPS


數學, 組合, 計算同側異側

 

#include <stdio.h>

int main() {
    int n, m, i, j, cases = 0;
    double a[3005], b[3005], c[3005];
    double x[105], y[105];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            scanf("%lf %lf %lf", &a[i], &b[i], &c[i]);
        scanf("%d", &m);
        for(i = 0; i < m; i++)
            scanf("%lf %lf", &x[i], &y[i]);
        long long ret = 0;
        for(i = 0; i < m; i++) {
            int neg = 0, pos = 0;
            for(j = 0; j < n; j++) {
                if(a[j]*x[i] + b[j]*y[i] + c[j] < 0)
                    neg++;
            }
            pos = n-neg;
            ret += pos*(pos-1)/2;
            ret += neg*(neg-1)/2;
        }
        printf("Roadmap %d:\n", ++cases);
        printf("Negative Builders Ltd. will build %lld New Roads.\n", ret);
    }
    return 0;
}

台長: Morris
人氣(469) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 517 - Word
此分類上一篇:[UVA] 11058 - Encoding

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文