Congruent trianglesProblem code: H3 |
All submissions for this problem are available.
After learning about congruent triangles in his recent mathematics lesson, Johnny has become very excited. He has even invented an interesting counting problem involving congruent triangles!
Recall that two triangles are congruent if their corresponding sides are equal in length and their corresponding angles are equal in size. A lattice triangle is a triangle such that the coordinates of all its vertices are integers. Johnny's problem can now be described as follows:
You are given an integer M and a lattice triangle ABC all of whose vertices (A, B, and C) are inside rectangle RM. RM is the rectangle having (0,0) as its bottom-left corner and (M,M) as its top-right corner. In other words, 0 ≤ xA, yA, xB, yB, xC, yC ≤ M. The problem is to count the number of lattice triangles congruent to ABC also having all their vertices inside the rectangle RM.
Could you help Johnny write a program to solve this problem?
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case has the following form:
- The first line contains two numbers M and K (1≤ M ≤ 1000, 1≤ K ≤1000). K is the number of given triangles.
- Each line in the next K lines contains 6 integers xA, yA, xB, yB, xC, yC (0 ≤ xA, yA, xB, yB, xC, yC≤ M) describing a triangle ABC. It is guaranteed that ABC is always a triangle (i.e., non-degenerate).
The input for successive test cases is separated by a blank line.
Output
For each test case, output a line containing the string "Case #T:" where T should be replaced by the corresponding test case number.
Then, K lines should follow, each line containing the number of triangles having vertices inside the rectangle RM, congruent to the corresponding triangle given in the input.
Print a blank line after each test case.
Example
Input: 2 2 2 0 0 0 2 2 0 0 0 1 1 2 0 3 2 0 0 0 2 2 0 0 0 1 1 2 0 Output: Case #1: 4 8 Case #2: 16 24
Output details
The 8 triangles congruent to the second triangle (in the first test case) are presented in the following figure:
| Date: | 2009-09-15 |
| Time limit: | 1s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 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 CAML CLPS PRLG WSPC BF ICK TEXT |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can I get more test cases for
Currently it is not possible
Currently it is not possible to get more test cases as the contest is on.
Should we print an empty line
Should we print an empty line between tests cases or also after last test case?
Print a blank line after
Print a blank line after every test case.
wont you be thinking that the
wont you be thinking that the second triangle (in the first test case) should have more congruent triangles.. as you have not considered most of its congruent triangles.
1. angle B at each of the corners of the rectangles.
They must be lattice
They must be lattice triangles; the ones you mentioned are not.
In the first triangle of
In the first triangle of second test case shouldn't there be 8 triangles as the sideways triangle would overlap with the top down triangles.If not can u tell me how the 16 are formed
The problem doesn't say
The problem doesn't say anything about triangles overlapping.
@Nitin Youre right that would
Hi, i am getting compilation
Hi,
i am getting compilation error for my submissions. Is there anyway I can find out what are compilation errors.
Anil
@ Shashank - no it won't. The
@ Shashank - no it won't. The distance from A to B isn't an integer.
Is a mirror image of a
I think the description and
I think the description and in particular the pictures at the bottom are pretty clear about that..
Hello, for the first test
Then you are incorrect.
Then you are incorrect.
my code is showing run time
my code is showing run time eror
how can i know eror code
or can i get the input on which it is tested so that even i can test
is (0,0),(0,1),(2,0) and
@Shahzor - Yes.
@Shahzor - Yes.
package
package com.abhi.triangles;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class CongruentCalculator {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int numerOfTestCases = Integer.parseInt(in.readLine());
for (int n = 0; n < numerOfTestCases; n++) {
out.println("Case #" + (n + 1) + ":");
in.readLine();
String s = in.readLine();
int idx = s.indexOf(' ');
int m = Integer.parseInt(s.substring(0, idx));
int K = Integer.parseInt(s.substring(idx + 1));
int N = (m + 1) * (m + 1);
for (int k = 0; k < K; k++) {
StringTokenizer st = new StringTokenizer(in.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
int x3 = Integer.parseInt(st.nextToken());
int y3 = Integer.parseInt(st.nextToken());
int counter = 0;
ThreePointSet triangle = getThreePointsSet(x1, x2, x3, y1, y2,
y3, m);
for (int p = 1; p <= N - 2; p++) {
for (int q = p + 1; q <= N - 1; q++) {
for (int r = q + 1; r <= N; r++) {
ThreePointSet threePointSet = new ThreePointSet(p,
q, r, m);
if (triangle.isEqual(threePointSet)) {
counter += 1;
}
}
}
}
out.println(counter);
}
out.println();
}
out.close();
}
public static ThreePointSet getThreePointsSet(int x1, int x2, int x3,
int y1, int y2, int y3, int m) {
int d1 = ThreePointSet.getSquaredDistance(x1, y1, x2, y2);
int d2 = ThreePointSet.getSquaredDistance(x1, y1, x3, y3);
int d3 = ThreePointSet.getSquaredDistance(x2, y2, x3, y3);
Set<Integer> distanceSet = new HashSet<Integer>();
distanceSet.add(d1);
distanceSet.add(d2);
distanceSet.add(d3);
return new ThreePointSet(getPoint(x1, y1, m), getPoint(x2, y2, m),
getPoint(x3, y3, m), m, distanceSet);
}
public static int getPoint(int x1, int y1, int m) {
return (m + 1) * x1 + y1 + 1;
}
}
package com.abhi.triangles;
import java.util.HashSet;
import java.util.Set;
public class ThreePointSet {
int p1;
int p2;
int p3;
int boundary;
Set<Integer> distanceSet;
ThreePointSet(int p1, int p2, int p3, int boundary, Set<Integer> distanceSet) {
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
this.boundary = boundary;
this.distanceSet = distanceSet;
}
ThreePointSet(int p1, int p2, int p3, int boundary) {
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
this.boundary = boundary;
}
public boolean isEqual(Object o) {
ThreePointSet otherPointsSet = (ThreePointSet) o;
Set<Integer> otherPointDistanceSet = getDistanceSet(otherPointsSet);
return distanceSet.equals(otherPointDistanceSet);
}
public int getX(int point) {
if (point % (boundary + 1) != 0) {
return point / (boundary + 1);
} else
return (point / (boundary + 1)) - 1;
}
public int getY(int point) {
if (point % (boundary + 1) != 0) {
return (point % (boundary + 1)) - 1;
} else
return boundary;
}
Set<Integer> getDistanceSet(ThreePointSet points) {
int p1 = points.p1;
int p2 = points.p2;
int p3 = points.p3;
int x1 = getX(p1);
int x2 = getX(p2);
int x3 = getX(p3);
int y1 = getY(p1);
int y2 = getY(p2);
int y3 = getY(p3);
int d1 = getSquaredDistance(x1, y1, x2, y2);
int d2 = getSquaredDistance(x1, y1, x3, y3);
int d3 = getSquaredDistance(x2, y2, x3, y3);
Set<Integer> distanceSet = new HashSet<Integer>();
distanceSet.add(d1);
distanceSet.add(d2);
distanceSet.add(d3);
return distanceSet;
}
public static int getSquaredDistance(int x1, int y1, int x2, int y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
}