SPOJ: GAME OF LINES

                                 

3184. Game of Lines

Problem code: LINES

Link to problem: http://www.spoj.com/problems/LINES/

SOLUTION: find number of all different slopes possible.

All slopes:

can be found in O(n^2) time by considering all possible combinations.

Different slopes:

How to remove or detect duplicate value of slopes?
STL library class set is the data structure which should be used as it contains only unique keys.Map can also be used but set will serve our purpose better.

Slopes:
Slopes can be stored in set in two ways.

1) double slope, but  can be a possible source of WA (wrong answer) for various reasons.
2) int mx=(x2-x1) , my=(y2-y1); 

    m=gcd(mx,my);
    mx/=m; my/=m;

    now pair(mx,my) can be inserted into the set. 

SOURCE CODE:

#include<stdio.h>
#include<map>
#include<set>
#include<algorithm>
#include<iostream>
#include<limits.h>
using namespace std;

int gcd(int m,int n)
{
if(m==0)return n;
return gcd(n%m,m);
}

int main()
{
int n;
scanf("%d",&n);
while(n!=0)
{
set<pair<int,int> > mp;
int i,x[n],y[n],j;
for(i=0;i<n;i++)
   scanf("%d %d",&x[i],&y[i]);
 int mx,my,m;
for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
  {
   my=(y[j]-y[i]);
   mx=(x[j]-x[i ]);
   m=gcd(mx,my);
   if(m!=0){
  my/=m;mx/=m;
  if(mx<0)
  {mx*=-1;my*=-1;}
  }
  mp.insert(make_pair(mx,my));
  }
}
  printf("%d\n",mp.size());
  scanf("%d",&n);
}

return 0;}