Cell Phone Towers

Problem code: L1

All submissions for this problem are available.

Byteline is currently the largest mobile phone operator in Byteland. They have N cellphone towers at different places in Byteland.

Byteland can be viewed as a two dimensional plane, with each tower or skyscraper described by a point in that plane. Of course, no two points have the same coordinates.

Two towers can only communicate with each other if there is no tower nor skyscraper lying on the straight line segment connecting them.

As the most skillful programmer in the company, Johnny's job is to write a program to help Byteland compute the number of pairs of towers which can communicate with each other.

And once again, Johnny has asked for your help!

Input

The first line contains a number t (about 15) which is the number of test cases. Then t test cases follow. Each test case has the following form.

The first line contains two numbers N and M (1 <= N, M <= 1000), the number of towers and skyscrapers in Byteland.

Each line in the next N lines contains two integers representing the coordinates of the cellphone towers.

Finally, each line in the next M lines contains two integers representing the coordinates of the skyscrapers.

All coordinates have absolute values not larger than 10000.

Output

For each test case, print a single number, describing the number of pairs of towers which can communicate with each other.

Example

Input
1
5 4
-1 -1
1 -1
0 -2
-2 -2
0 0
-1 -2
1 0
-1 1
0 -1

Output
6

Output details

In the above figure, the blue points represent the cell towers and the red points represent the skyscrapers as in the example input. The 6 segments AE, BE, BC, AC, AD and BD correspond to the 6 pairs of towers that can communicate with each other.

Date: 2009-12-15
Time limit: 3

s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK TEXT JS


Comments

can you plese let me know why

sandeepkkothari @ 1 Jan 2010 08:19 PM

can you plese let me know why the solution I submitted shows time limit exceeded...

No, not until after the

triplem @ 2 Jan 2010 07:52 AM

No, not until after the contest has finished.

HI everyone, i am newbie to

mainak @ 2 Jan 2010 11:28 AM

HI everyone,

i am newbie to programming contests. I want to know how i can measure the running time for a given number of operations. Yes, I learnt about complexity analysis. but how to measure how much time will 10000 operations take? for example

for(i=0;i<10000;i++)

scanf("%d",&array[i]);

 

how much time in seconds will this snippet take to execute here on this server? can i measure this time on my computer?

thanks in advance.

@Mainak: we can't be our

jcomeau_ictx @ 2 Jan 2010 11:58 AM

@Mainak: we can't be our usual helpful selves during contests. You'll have to ask in other venues or wait until after the contest is over.

Hello Guys, I am New to this

hiren.sharma @ 3 Jan 2010 12:05 AM

Hello Guys, I am New to this Site so plz telle me if I Can post the Programs written in Turbo C++, If yes then do we have to Submit the .c file or the exe file

@Hiren: the source (.c or

jcomeau_ictx @ 3 Jan 2010 01:38 AM

@Hiren: the source (.c or .cpp) file, not the executable.

I have solved this problem on

vishnu.mnnit @ 3 Jan 2010 04:25 AM

I have solved this problem on my gcc compiler but when i submit same program here its giving timeout error..

plz help.

What is the memory limit for

rajatag12 @ 3 Jan 2010 09:35 PM

What is the memory limit for this problem?

@Rajat The standard memory

admin @ 4 Jan 2010 03:51 PM

@Rajat The standard memory limit. 64 Mb is guaranteed.

Is there any way to find out

ankul_iiita @ 4 Jan 2010 04:17 PM

Is there any way to find out by how much is my program getting TLE?

Not really, no.

triplem @ 4 Jan 2010 04:19 PM

Not really, no.

Can we get to know about the

bansal.prateek @ 5 Jan 2010 08:43 PM

Can we get to know about the time the code is taking in case of "time limit exceeded", so that we may decide whether to use a different approach or to just optimize the current code???

Time limit exceeded for me

rak19 @ 7 Jan 2010 06:40 PM

Time limit exceeded for me too.

Can anybody give me some tips

amir_003 @ 9 Jan 2010 01:03 AM

Can anybody give me some tips to minimize the running time of my program.

Yeah, time limit is a

Code8 @ 9 Jan 2010 01:52 AM

Yeah, time limit is a problem. Great contest as usual though. Keep em coming... :o)

Is the time limit for JAVA is

ahmed_aly @ 9 Jan 2010 02:42 AM

Is the time limit for JAVA is the same as for C++?

No, the time limit is doubled

triplem @ 9 Jan 2010 03:06 AM

No, the time limit is doubled for Java. Read the FAQ.

I m new to this contest. I

amir_003 @ 10 Jan 2010 02:03 AM

I m new to this contest.

I want to know how the in put is going to be taken? Is it from user input or a file is to used.

If a file is used then what should be its name?

Standard input/output

triplem @ 10 Jan 2010 02:42 AM

Standard input/output streams.

In my C compiler the time

amir_003 @ 10 Jan 2010 03:04 PM

In my C compiler the time taken gives in time..

But in submission it shows exceeded.

I cant get how??

The judge tests your code on

admin @ 12 Jan 2010 03:44 PM

The judge tests your code on test cases other than the sample ones. You might not have an exhaustive data set at your end.

Very much a work of Stephen

ajay_vishnu @ 12 Jan 2010 11:55 PM

Very much a work of Stephen :p,  seeing the graph & his activeness here.... anyway back to problem.

For my program time limit has

master @ 13 Jan 2010 06:44 PM

For my program time limit has expired

but the mem used is 0M ......why?????

So.. whats the solution ?

abhijith @ 15 Jan 2010 03:29 PM

So.. whats the solution ?

@Admin Can we get the input

chandan @ 15 Jan 2010 08:03 PM

@Admin

Can we get the input files for these problems??

"All coordinates have

vector9x @ 15 Jan 2010 11:41 PM

"All coordinates have absolute values not larger than 10000."

 

But in the uru's solution he uses:

COORD_MAX=1000;
...
obstacles : array[-COORD_MAX..COORD_MAX,-COORD_MAX..COORD_MAX] of boolean;

why his solution passes?

there is not a test case with coordinates greather than 1000 ??

So, altought the problem statement says the limits, i can to try weak solutions and may be this passes... it's not good :(

I want to submit solution. I

kapilreddy @ 16 Jan 2010 03:14 PM

I want to submit solution. I think I got it right and want to check out with chef. Is there anyway I can submit after competition is finished

Are the test cases for this

devvrr @ 23 Jan 2010 08:56 AM

Are the test cases for this problem pubic now?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions