Congruent triangles

Can I get more test cases for this problem? I've cross checked my result using brute force, I dont know why it always says "Wrong answer"

Currently it is not possible to get more test cases as the contest is on.

Should we print an empty line between tests cases or also after last test case?

Print a blank line after every test case.

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 triangles; the ones you mentioned are not.

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 anything about triangles overlapping.

@Nitin Youre right that would make more cases.. @Stephen Consider B at corners... the triangles will still be lattice...

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 distance from A to B isn't an integer.

Is a mirror image of a triangle considered to be congruent? for example: is [(0,0),(1,0),(2,2)] congruent with [(2,2),(3,0),(4,0)]?

I think the description and in particular the pictures at the bottom are pretty clear about that..

Hello, for the first test case's first sub-case, involving (0,0),(0,2),(2,0) vertices, I am getting 8 congruent triangles, not 4, in a 2*2 box.

Then you are incorrect.

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 (0,0),(2,0),(2,1) also considered congruent??

@Shahzor - Yes.

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);
}

}