## 184 - Laser Lines

Moderator: Board moderators

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

### 184 help~~~~

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:
in case you have not notice, the 2 x&&y should be x||y

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

### 184 - Laser Lines

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

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

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 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{

point pts[350];
point list[350][50];

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 ii,jj,kk;
/*Searching*/
for (ii=0;ii<n;ii++){
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;
}else{
}
next = 0;
next = 1;
break;
}
if (next == 1)
continue;
for (kk=jj+1;kk<n;kk++){
}else{
}
if (cnt == 0){
cnt = 3;
}else{
cnt++;
}
}
}
if (cnt > 0){
}
}
}
/*Output*/
printf("No lines were found\n");
else{
printf("The following lines were found:\n");
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;
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:

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``````

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
Thanks alot!

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
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:

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

Code: Select all

``````removed AC code ...
``````

epstein
New poster
Posts: 1
Joined: Wed Aug 17, 2005 12:04 pm
hi,
does anyone have nice large, (difficult?!) input for this problem??

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

yin_yang2k
New poster
Posts: 4
Joined: Wed Jul 05, 2006 6:50 pm
Location: Sweden
Is there some kind of famous algorithm for this problem witch solves it the most efficient way? Like the