Nice QuadranglesProblem code: NICEQUAD |
All submissions for this problem are available.
There are n points with integer coordinates. We can form different quadrangles out of them by taking four different points and connecting them with lines. Let s call a quadrangle ABCD nice if and only if:
- Ax > 0 and Ay > 0;
- Bx > 0 and By < 0;
- Cx < 0 and Cy < 0;
- Dx < 0 and Dy > 0;
- ABCD has an integer area.
Your task is to count all different nice quadrangles that can be formed on the given points.
Input
The first line of input file contains number t the number of test cases. Then the description of each test case follows. The first line of each test case contains number n the number of points. Then n lines follow each consisting of two integers x, y the coordinates of a point. No two points in the same test case coincide.
Constraints
1 <= t <= 10
1 <= n <= 30000
-30000 <= x, y <= 30000
Output
For each test case print the number of nice quadrangles that can be formed using given points.
Example
Input: 1 6 1 1 2 2 -1 -1 -2 2 2 -1 -3 -4 Output: 2
| Author: | spooky |
| Date Added: | 9-04-2010 |
| Time Limit: | 1 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, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
can you explain how answer is
can you explain how answer is 2.
According to my understanding is will be 4 the quardangles are.
1> (1,1) (2,-1) (-3,-4) (-2,2)
2> (1,1) (2,-1) (-1,-1) (-2,2)
3> (2,2) (2,-1) (-3,-4) (-2,2)
4> (2,2) (2,-1) (-1,-1) (-2,2)
or sorry got it.
or sorry got it.
can you explain how answer is
can you explain how answer is 2????
Comment edited by Admin
Comment edited by Admin
@Amit. Posting or asking for
@Amit. Posting or asking for hints is not permitted. Violation of rules may lead to banning in future contests.
@Admin: none of the Java
@Admin: none of the Java programs so far have been successful - or even gotten wrong answers. we all keep timing out! i've gone to crazy lengths to optimize on this particular problem. i'll get banned if i say any more on that. just one request please, can one of you guys higher up actually code this in Java and measure us against that, instead of doubling the default time limit? so we'll at least know whether we're on the right algorithm, or just forever wrong because of our choice of language?
@Admin : Sorry for that
@Admin : Sorry for that comment.
May i ask what an integer
May i ask what an integer area is?
OK, my question is about "all
OK, my question is about "all different nice quadrangles". Does it mean different shape of the quadrangles? For example following coordinates describes one quadrangle (square) but placed elsewhere in the coordinate system (ABCD and EFGH):
A(-3,3), B(3,3), C(3,-3), D(-3,-3), E(-2,2), F(4,2), G(4,-4), H(-2,-4)
Please explain me if those quadrangles (ABCE and EFGH) are the same in meaning from description of task.
@Brien an integer area is
@Brien an integer area is that which has a whole number as its value. e.g.:
if a quadrangle has an area of 22.5 units, that is not an integer area.
if a quadrangle has an area of 17 units, that is an integer area.
Hmmm... sorry for my stupid
Hmmm... sorry for my stupid question. It's explained in Qutput section: "For each test case print the number of nice quadrangles that can be formed using given points.".
beautiful; i submitted code
beautiful; i submitted code (in Java) that reads all the input and prints a single "0" per test case, no computations; it timed out.
18th submission finally got
18th submission finally got AC. Phew!!
i'm also a programmer in java
i'm also a programmer in java but i'm a high school student and i think all other programmers in JAVA should be satisfied with their programmes if they run successfully in their respective PCs. if they can they should start up their own ONLINE ''JAVA" programming competetion. i'd be waiting for that
I am a Java programmer and I
I am a Java programmer and I believe java programmer are not in a downside of advantage as we are given 2x time limits. tweak your algos . i have been participating for while and I can say this with confidence.
Yeah, you need to prune your
Yeah, you need to prune your I/O code to be efficient as well. Personally, I find it unfortunate that I/O must also be tweaked to get below the time limit, but apparently it can be done. Fear not, once you optimize your I/O once, you can recycle that piece for the next n times :D
@admins : The judge gives a
@admins : The judge gives a Wrong answer just at the first case it finds wrong instead of evaluating the whole set of test cases and then showing TLE or WA according to the submission. As a result, even the codes that will TLE on large test cases and giving wrong answer for smaller test cases do give WA instead of TLE. This is really confusing :( Judge's checker needs to be modified or the largest test case should be there in the beginning of test cases.
@Ankul: There can be multiple
@Ankul: There can be multiple test files.So, it's better to submit a correct code instead of experimenting with the test cases :D
9th submission and its
9th submission and its correct... my first solution in a running contest... and ya java works fine.. no probs with that.. optimise ur algo... :) :)
My name is not in over all
My name is not in over all ranking list?
if 3 points out of the 4 are
if 3 points out of the 4 are collinear, will it still be considered a valid quadrangle?
That question does not need
That question does not need to be answered.
Should we take the input from
Should we take the input from the file or from the command line??
i dont like the new code
i dont like the new code submit interface (with color, line ...) . thus a simple one? How can I obtain it? There is an option to do it?