184 - Laser Lines

obayashi · Post by **obayashi** » Tue Aug 20, 2002 1:21 pm

i cannot find the problem with my code~

[cpp]
#include <iostream>
#include <iomanip>
#include <memory.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
int x,y;
} point_t;
point_t pt[300];
int num,used[300][300];
const double VERT = 1e30;
inline int cmp (const void *a,const void *b) {
point_t *t1,*t2;
t1 = (point_t*)a;
t2 = (point_t*)b;
if (t1->x<t2->x) {
return -1;
} else if (t1->x>t2->x) {
return 1;
} else {
return t1->y<t2->y?-1:t1->y>t2->y?1:0;
}
}
void solve () {
qsort(pt,num,sizeof(point_t),cmp);
int flag = 0;
for (int i=0;i<num-1;i++)
for (int j=i+1;j<num;j++) {
double ko,kc;
int first = 1, p[300], dup = 0, pre;
if (pt.x==pt[j].x)
ko = VERT;
else
ko = double(pt.y-pt[j].y)/(pt.x-pt[j].x);
pre = j;
p[dup++] = i;
p[dup++] = j;
for (int k=j+1;k<num;k++) {
if (used[pre][k]) continue;
if (pt[pre].x==pt[k].x)
kc = VERT;
else
kc = double(pt[pre].y-pt[k].y)/(pt[pre].x-pt[k].x);
if (fabs(ko-kc)<1e-8) {
if (!flag) {
cout<<"The following lines were found:"<<endl;
flag = 1;
}
if (first) {
first = 0;
cout<<"("<<setw(4)<<pt.x<<","<<setw(4)<<pt.y<<")";
cout<<"("<<setw(4)<<pt[pre].x<<","<<setw(4)<<pt[pre].y<<")";
}
cout<<"("<<setw(4)<<pt[k].x<<","<<setw(4)<<pt[k].y<<")";
p[dup++] = k;
pre = k;
}
}
if (!first) {
cout<<endl;
for (int l=0;l<dup-1;l++)
for (int m=l+1;m<dup;m++)
used[p[l]][p[m]] = used[p[m]][p[l]]= 1;
}
}
if (!flag) cout<<"No lines were found"<<endl;
}
int main () {
int x,y;
cin>>x>>y;
while (x && y) {
num = 0;
memset(used,0,sizeof(used));
while (x && y) {
int flag = 1;
for (int i=0;i<num;i++)
if (pt.x==x && pt.y==y) {
flag = 0;
break;
}
if (flag) {
pt[num].x = x;
pt[num].y = y;
num++;
}
cin>>x>>y;
}
solve();
cin>>x>>y;
}
return 0;
}

[/cpp]

yiuyuho · Post by **yiuyuho** » Mon Dec 01, 2003 4:55 am

in case you have not notice, the 2 x&&y should be x||y

sohel · Post by **sohel** » Tue Oct 12, 2004 2:10 pm

This should be or seems to be a straight forward problem..
.. but as usual I am getting WA.
The sad part is there is no other thread related to this problem, which means every one is getting AC in one go.

My algorithm is straight forward n^3 and I use atan2() function for checking equal gradients. And I also ensure that the same line is not represented twice.

Is there anything wrong with my approach or is it one of those precision error prone problems.

Anyone willing to share some ideas..

Heartattack! · Post by **Heartattack!** » Thu Nov 11, 2004 5:23 pm

Ok, why on earth would you want to use gradients? Say you got three points a,b,c.

int pos=a.x*b.y + b.x*c.y + c.x*a.y;
int neg=a.x*c.y + b.x*a.y + c.x*b.y;

if(pos==neg)
/*They're on the same line*/

You can do it with just ints. Not a single floating point is needed. Good luck.

Heartattack! · Post by **Heartattack!** » Thu Nov 11, 2004 5:27 pm

Ok, why on earth would you want to use gradients? Say you got three points a,b,c.

int pos=a.x*b.y + b.x*c.y + c.x*a.y;
int neg=a.x*c.y + b.x*a.y + c.x*b.y;

if(pos==neg)
/*They're on the same line*/

You can do it with just ints. Not a single floating point is needed. Good luck.

roticv · Post by **roticv** » Mon Jul 04, 2005 7:47 am

I'm facing the same problem - I keep getting WA. I'm not sure what is wrong, hopefully someone would look into my code.

Code: Select all

#include <stdio.h>

typedef struct{
int x;
int y;
}point;

typedef struct{
int grady;
int gradx;
}gradient;

point pts[350];
gradient gra[350];
point list[350][50];
int flag, n,ngrad,x,y,i;

int GCD(int a,int b) {
	int tmp;
	if (b > a){
		tmp = a;
		a = b;
		b = tmp;
	}
	while (b > 0) {
		a = a % b;
		a ^= b;
		b ^= a;
		a ^= b;
	}
	return a;
}

int compare(const void* a, const void* b){
	point *pt1, *pt2;
	pt1 = (point*)a; pt2 = (point*)b;
	if (pt1[0].x > pt2[0].x)
		return 1;
	if (pt1[0].x == pt2[0].x)
		if (pt1[0].y > pt2[0].y)
			return 1;
	return -1;
}

void dostuff(){
	int grady,gradx,grady2, gradx2, gcd,next,cnt;
	int ii,jj,kk;
	/*Searching*/
	for (ii=0;ii<n;ii++){
		gra[ii].grady = 0; gra[ii].gradx = 0;
		for (jj=0;jj<n;jj++){
			list[ii][jj].x = 0; list[ii][jj].y = 0;
		}
	}
	for (ii=0;ii<n-2;ii++){
		for (jj=ii+1;jj<n-1;jj++){
			cnt = 0;
			grady = pts[jj].y - pts[ii].y;
			gradx = pts[jj].x - pts[ii].x;
			gcd = GCD(abs(grady),abs(gradx));
			grady /= gcd; gradx /= gcd;
			if (grady < 0 && gradx < 0){
				grady = -grady; gradx = -gradx;
			}else{
				if (gradx < 0){ grady = -grady; gradx = -gradx;}
			}
			next = 0;
			for (kk = 0;kk<ngrad;kk++)
				if (gra[kk].grady == grady && gra[kk].gradx == gradx){
					next = 1;
					break;
				}
			if (next == 1)
				continue;
			for (kk=jj+1;kk<n;kk++){
				grady2 = pts[kk].y - pts[ii].y;
				gradx2 = pts[kk].x - pts[ii].x;
				gcd = GCD(abs(grady2),abs(gradx2));
				grady2 /= gcd; gradx2 /= gcd;
				if (grady2 < 0 && gradx2 < 0){
					grady2 = -grady2; gradx2 = -gradx2;
				}else{
					if (gradx2 < 0){ grady2 = -grady2; gradx2 = -gradx2;}
				}
				if (gradx == gradx2 && grady == grady2){
					if (cnt == 0){
						gra[ngrad].grady = grady; gra[ngrad].gradx = gradx;
						list[ngrad][0].y = pts[ii].y; list[ngrad][0].x = pts[ii].x;
						list[ngrad][1].y = pts[jj].y; list[ngrad][1].x = pts[jj].x;
						list[ngrad][2].y = pts[kk].y; list[ngrad][2].x = pts[kk].x;
						cnt = 3;
					}else{
						list[ngrad][cnt].y = pts[kk].y;
						list[ngrad][cnt].x = pts[kk].x;
						cnt++;
					}
				}
			}
			if (cnt > 0){
				list[ngrad][cnt].y = 0; list[ngrad][cnt].x = 0;
				ngrad++;
			}
		}
	}
	/*Output*/
	if (ngrad == 0)
		printf("No lines were found\n");
	else{
		printf("The following lines were found:\n");
		for (ii=0;ii<ngrad;ii++){
			for (jj=0;;jj++){
				if (list[ii][jj].y == 0 && list[ii][jj].x == 0)
					break;
				printf("(%4d,%4d)",list[ii][jj].x,list[ii][jj].y);
			}
			printf("\n");
		}
	}
	return;
}

int main(){
	int flag2;
	flag = 1;
	for (;;){
		scanf(" %d %d",&x,&y);
		if (x == 0 && y == 0){
			if (flag == 1)
				break;
			qsort(pts,n,sizeof(point),compare);
			dostuff();
			n = 0;
			ngrad = 0;
			flag = 1;
			continue;
		}
		if (x < 0 || y < 0)
			continue;
		flag = 0;
		flag2 = 0;
		for (i=0;i<n;i++)
			if (pts[i].x == x && pts[i].y == y){
				flag2 = 1;
				break;
			}
		if (flag2 == 0)
			pts[n].x = x; pts[n].y = y; n++;
	}
	return 0;
}

Ruslan Shevelyov · Post by **Ruslan Shevelyov** » Wed Jul 06, 2005 2:51 pm

Code: Select all

1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 0 0
0 0

Your program's output:

Code: Select all

The following lines were found:
(   1,   1)(   1,   2)(   1,   3)
(   1,   1)(   2,   1)(   3,   1)
(   1,   1)(   2,   2)(   3,   3)
(   1,   3)(   2,   2)(   3,   1)

Correct output:

Code: Select all

The following lines were found:
(   1,   1)(   1,   2)(   1,   3)
(   1,   1)(   2,   1)(   3,   1)
(   1,   1)(   2,   2)(   3,   3)
(   1,   2)(   2,   2)(   3,   2)
(   1,   3)(   2,   2)(   3,   1)
(   1,   3)(   2,   3)(   3,   3)
(   2,   1)(   2,   2)(   2,   3)
(   3,   1)(   3,   2)(   3,   3)

roticv · Post by **roticv** » Thu Jul 07, 2005 5:05 pm

Thanks alot!

roticv · Post by **roticv** » Thu Jul 07, 2005 5:51 pm

Weird, I fixed the problem you showed above and got your output, but i still got a WA.

Ruslan Shevelyov · Post by **Ruslan Shevelyov** » Thu Jul 07, 2005 9:30 pm

Code: Select all

if (flag2 == 0)
   pts[n].x = x; pts[n].y = y; n++;

Probably should be

Code: Select all

if (flag2 == 0){
   pts[n].x = x; pts[n].y = y; n++;
}

BTW, GCD is unnecessary. In fact, it is not obvious to me that this algorithm is correct. I used another:

Code: Select all

#include <list>
#include <vector>
#include <utility>
using namespace std;

typedef pair<int, int> point;
typedef vector<point> points;
typedef vector<point> line;
typedef list<line> lines;

// ...

void buildlines(points& p, lines& lns){
   for(int i=0; i < p.size()-2; i++){
      for(int j=i+1; j < p.size()-1; j++){
         line ln;
         ln.push_back(p[i]);
         ln.push_back(p[j]);
         for(int k=j+1; k < p.size(); k++){
            if((p[k].first - p[i].first) * (p[j].second - p[i].second)
                                         ==
               (p[k].second - p[i].second) * (p[j].first - p[i].first)){
                  ln.push_back(p[k]);
               }
         }
         if(ln.size() > 2)
            lns.push_back(ln);
      }
   }
}

geran · Post by **geran** » Wed Aug 03, 2005 12:48 am

edit: I submited as problem 148 instead of 184... my bad

Please help!!! I get Memory Limit Exceeded, can somebody please help me..

Code: Select all

removed AC code ...

epstein · Post by **epstein** » Wed Aug 17, 2005 12:06 pm

hi,
does anyone have nice large, (difficult?!) input for this problem??
Hopefully including the AC answer...

lovemagic · Post by **lovemagic** » Fri Jul 07, 2006 8:35 pm

can somebody post some test case?My code passed the cases found in the board but its getting WA!!!!

lovemagic · Post by **lovemagic** » Mon Jul 10, 2006 6:45 pm

got AC

yin_yang2k · Post by **yin_yang2k** » Mon Jul 17, 2006 9:40 pm

Is there some kind of famous algorithm for this problem witch solves it the most efficient way? Like the

OJ Board

184 - Laser Lines

184 help~~~~

184 - Laser Lines

Memory Limit Exceeded