184 - Laser Lines

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

184 help~~~~

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]
Time makes a fool of memory
And yet my memories still shine

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

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

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

184 - Laser Lines

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!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

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. 8) 8) 8) 8)
We will, We will BREAK LOOP!!!!

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

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. 8) 8) 8) 8)
We will, We will BREAK LOOP!!!!

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

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
New poster
Posts: 15
Joined: Fri Aug 08, 2003 8:13 pm
Location: Russia, Moscow
Contact:

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)
www.Find-a-Drug.org distributed computing project

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

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

Thanks alot!

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

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
New poster
Posts: 15
Joined: Fri Aug 08, 2003 8:13 pm
Location: Russia, Moscow
Contact:

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);
      }
   }
}
www.Find-a-Drug.org distributed computing project

geran
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Memory Limit Exceeded

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

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

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

Code: Select all

removed AC code ...

epstein
New poster
Posts: 1
Joined: Wed Aug 17, 2005 12:04 pm

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
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

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!!!!
khobaib

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

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

got AC :D
khobaib

User avatar
yin_yang2k
New poster
Posts: 4
Joined: Wed Jul 05, 2006 6:50 pm
Location: Sweden

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

Post Reply

Return to “Volume 1 (100-199)”