All submissions for this problem are available.

In an ants' colony spread over a flat surface, the ants can reside at integral coordinates as close as unit distance apart from each other (but no closer). The colony has the shape of a quadrilateral ABCD where one ant must reside at each of A, B, C, and D, and all other ants can be on any integral coordinate on its perimeter and its interior. Given the integral positions of A, B, C, and D, print the maximum number of ants that can reside in the colony (including the ants that can reside on the four corners and the perimeter).

Input

The first line contains the number of test cases, N.

For each test case, a single line contains the x and y coordinates of the four corners of the quadrilateral in clockwise order starting with the left-most, bottom-most point.

Output

For each test case, print the case number, followed by a colon, followed by a single space, followed by a single integer indicating the maximum number of ants.

Constraints

0 < N ≤ 3

|x|, |y| ≤ 10,000

Example

Input:
2
1 1 3 4 5 3 6 1
1 3 5 6 6 3 3 1

Output:
Case 1: 14
Case 2: 16

Give a 4-point polygon (integer coordinates), find out how many integer points inside or on the border of that polygon.

EXPLANATION:

This problem is really classical. Let me introduce the Pick's Theorem first.
Area = # Inner Integer Points + # Border Integer Points / 2 - 1


To calculate the Area, we can use cross product.

So the remain part is to get the number of integer points on its border. That equals to count how many integer points on the segment (0,0) - (dx, dy). This can be solved by Greatest Common Divisor (gcd).
# Integer Points on Segment = gcd(dx, dy) + 1


which including the two ends.

Combining these together and applying the Pick's Theorem, we finally get the total integer points inside or on the border.








1down vote


It is simply GCD(x1−x2,y2−y1)$GCD(x_1-x_2,y_2-y_1)$ . I can explain if anyone wants to, just because this post is so old , I dont think anyone will bother to see it

EDIT: Let the equation of line be :

y−y1x−x1$\frac{y-y1}{x-x1}$ = y2−y1x2−x1$\frac{y2-y1}{x2-x1}$

Now just switching the positions of these expressions we get:

y−y1y2−y1$\frac{y-y1}{y2-y1}$ = x−x1x2−x1$\frac{x-x1}{x2-x1}$

Now , y - y1 should be equal to k * y2−y1GCD(y2−y1,x2−x1)$\frac{y2-y1}{GCD(y2-y1,x2-x1)}$ .

Why ? x should be integer! if we write x in terms of everything else We will see
y−y1y2−y1$\frac{y-y1}{y2-y1}$ should be Integer.

Now I say that k1=0 Gives me y1 , to find the final kn , I put y= y2 into this equation (x2,y2 is the last integral point) .

That gives me kn=GCD(y2−y1,x2−x1)$GCD(y2-y1,x2-x1)$ . Now , every k between 0 and this kn are integral points!

If you include the initial point too ans is GCD(y2−y1,x2−x1)$GCD(y2-y1,x2-x1)$ +1 .

If you exclude initial and final points ans is GCD(y2−y1,x2−x1)$GCD(y2-y1,x2-x1)$ -1.









           Code goes here.....







#include<iostream>

#include<bits/stdc++.h>

#define ll long long int 

using namespace std;

int main()

{

 int t;

 cin>>t;

 for(int tt=1;tt<=t;tt++)

 {

    ll x1,y1,x2,y2,x3,y3,x4,y4;

    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;

   ll  A= (x1*y2-x2*y1)+(x2*y3-y2*x3)+(x3*y4-y3*x4)+(x4*y1-y4*x1);

   if(A<0)

   A=-A;

 //  cout<<A<<endl;

   A=A/2;

   ll i1,i2,i3,i4;

   i1=__gcd(abs(x1-x2),abs(y1-y2))+1;                         // x1 x2

   i2=__gcd(abs(x2-x3),abs(y2-y3))+1;

   i3=__gcd(abs(x3-x4),abs(y3-y4))+1;

   i4=__gcd(abs(x4-x1),abs(y4-y1))+1;

   ll i=i1+i2+i3+i4-4;

   ll by=i/2;

   ll interiors=(A+1)-by;

   cout<<"Case "<<tt<<": "<<i+interiors<<endl;

 }

 return 0;

}