## 10790 - How Many Points of Intersection?

Moderator: Board moderators

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Contact:
shamim wrote:
ibrahim wrote:What will be the output for 20000 20000 input.
3997800100000000
Dear shamim , thanks for your output. though i got AC, but my output for 20000 20000 is not same as you.
39996000100000000 (__int64 in VC6).
But after submit using long long i got accept . Someone please tell me how it's possible.
I think the output of __int64 and long long will be same. Am I right?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I also got 39996000100000000..

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
I would also suggest to calculate result in such way that no temporary value is bigger than result. This way we can be sure that there is no overflow if final result fits into int64.

E.g. for formula a*b/3 (divisibility presumed) it would be good idea to write:
r = a%3==0 ? a/3*b : b/3*a

Otherwise cases like a=0x7FFFFFFFFFFFFFFF, b=3 won't work.

Also make sure that best path checker does not suffer from overflowing itself. In example above we use % operator which does not suffer. But for formula a*b*c/6 one could test a*b, a*c, b*c against divisibility by 6 (after testing a, b, c themselves) which might overflow before applying % operator. Split 6 to 2*3 and reduce by 2 and 3 independently.
To be the best you must become the best!

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

### Sorry but what here wrong?

o:comp;function T(a:longint):longint;begin t:=a*(a-1)div 2;end;
begin n:=0;
repeat
if(a=0)and(b=0)then break;
o:=t(a); o:=o*T(b);
inc(n);
writeln('Case ',n,': ',o:0:0);
until false;
end.

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

### 10790 WA

Can u guys tell me why it didn't be C(m,2) * C(n,2) be the answer???

PLS...

Code: Select all

``````
#include <iostream>
using namespace std;
long long int gcd(long long int,long long int);

unsigned long long int c(int,int);
int main(void){
int a,b,d;
d=1;
while(cin>>a>>b){
if(a==0 && b==0){
break;
}
cout<<"Case "<<d++<<": "<<c(a,2)*c(b,2)<<endl;

}
//system("pause");
return 0;
}

unsigned long long int c(int a,int b){
unsigned long long int k,l,m;
int i;
k=1;
l=1;
if(a-b<b){
b=a-b;
}
for(i=1;i<=b;i++,a--){
k*=a;
l*=i;
m=gcd(k,l);

l/=m;
k/=m;
}
k/=l;

return k;
}
long long int gcd(long long int a,long long int b){
int tmp;
if(a>=b){tmp=a;
a=b;
b=tmp;
}
while(b%a!=0){
b=a%b;
tmp=a;
a=b;
b=tmp;
}
return a;
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
C(a,2) * C(b,2) is a correct formula.

But why are you trying to compute C(n,2) in such a complicated way?
C(n,2) is just n*(n-1)/2.

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

### Thank u

Thanks a lot .It's already AC.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Can someone post some more test cases (if possible) ?

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:
i think this problem has no critical i/o...some sample is follows...

Code: Select all

``````2 5
10 2
20 10
9 9
51 51
41 41
64 34
0 0

Case 1: 10
Case 2: 45
Case 3: 8550
Case 4: 1296
Case 5: 1625625
Case 6: 672400
Case 7: 1130976
``````
GOOD LUCK
Rocky

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Sorry, I posted in the wrong thread.
I needed test input for problem 11191 yesterday.
But I managed to find my mistake and I have it now ACC.
Thanks anyway.

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
why WA ???

Code: Select all

``````# include <iostream>

using namespace std;
int main()
{
int a,b,c=0;
while(cin>>a>>b)
{
++c;
if(a==0 && b==0)    return 0;
unsigned long long y=((a*(a-1))/2)*((b*(b-1))/2);
cout<<"Case "<<c<<": "<<y<<'\n';
}

return 0;
}
``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Your program actually does all its computations with 32-bit integers, and as a result it gets overflows.
Type of expressions in C++ is determined by the operands; so "((a*(a-1))/2)*((b*(b-1))/2)" is a perfectly valid int to the compiler, provided that a and b are int's.

mahi_seu.bd
New poster
Posts: 4
Joined: Mon Dec 06, 2010 8:25 pm
Contact:

### Re: 10790 - How Many Points of Intersection?

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
unsigned long a,b,i,j,sum,kes=0,p,k,sum1,sum2;
while(scanf("%lu%lu",&a,&b)==2){
if(a==0 && b==0) break;
sum=0;
k=0;
p=0;
kes++;
k=a-1;
p=b-1;
sum1=k*(k+1)/2;
sum2=p*(p+1)/2;
sum=(sum1*sum2);
printf("Case %lu: %lu\n",kes,sum);

}return 0;

}
I got ac.......

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

### Re: 10790 - How Many Points of Intersection?

Just got AC on this one.
The problem boils down to bijection of a choose 2 and b choose 2.
Which simplifies as stated by mf to

Code: Select all

``(a(a - 1)) / 2 * (b(b - 1)) / 2``

or even simpler

Code: Select all

``(a*b*(a-1)*(b-1)) / 4``
Be careful to use proper data types so input cases such as

Code: Select all

``````20000 20000
``````
provide the proper results