Cell Phone Towers

Problem code: L1

All Submissions

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.

Author:	admin
Date Added:	15-12-2009
Time Limit:	3 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC

Submit

Comments

Login or Register to post a comment.

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

http://www.codechef.com/probl

triplem @ 16 Jan 2010 03:30 PM

http://www.codechef.com/problems/L1/

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 non-commercial competitive programming community

In order to report copyright violations of any kind, send in an email to copyright@codechef.com

CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com

Site Navigation