143 - Orchard Trees

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

Should the judge tell us which test cases are messing us up?

Yes
17
52%
No
16
48%
 
Total votes: 33

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

Think about these questions:

1) Do you really need to scan all 100x100 trees to see if each one is inside the polygon?

2) If point i is inside, point i+1 is outside, when can point i+2 be inside?


ps: This method is just a pruning of your current method, which is also the method I used.. I managed to get AC in 2.1s, so it should be fine.
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

modified but WA

Post by sohel »

Thank you junbin for your hint.....
... I managed to avoid TLE but this time I am getting WA.

I have used almost all values for epsilon but still there seems to be some precision error.
Can someone who got AC verify my output for the following inputs:
[c]
1 2 3 5 6 9
1 1 2 2 3 3
5 4 3.2 3.6 1.0 0.6 1.2
1.1 1.1 2.2 2.2 5.5 10.3
6.2 6.63 2.36 3.21 3.32
0.0 0.0 100.0 100.0 100.0 0.0
0 0 0 0 0 0
[/c]

Output:
[c]
3
3
2
0
10
4950
[/c]

:x
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

Your output is correct.
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc »

Hey guys,

I get correct output too, but I still get WA. My input file is

Code: Select all

1.5 1.5  1.5 6.8  6.8 1.5
10.7 6.9  8.5 1.5  14.5 1.5
1 1 1 1 1 1
1 1 1 4 2 4
1 1 1 4 4 1
1 1 1 2 1 1
0 0 0 2 2 0
98 98 100 98 98 100
0 0 0 5 0.5 0
3.01 3.01 3.01 3.99 3.99 3.01
1 2 3 5 6 9
1 1 2 2 3 3
5 4 3.2 3.6 1.0 0.6 1.2
1.1 1.1 2.2 2.2 5.5 10.3
6.2 6.63 2.36 3.21 3.32
0.0 0.0 100.0 100.0 100.0 0.0 
0 0  0 0  0 0 
and my output is

Code: Select all

  15
  17
   1
   5
  10
   2
   1
   4
   0
   0
   3
   3
   2
   0
  10
4950
Is there some weird test data I'm missing? Can somebody supply a comprehensive test input with corresponding output, or at least give me a hint as to what makes this problem so tricky?[/code]
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc »

Hmm... I did a regex changing 'double' to 'long double' and it worked just fine. Seem to be getting a lot of stupid rounding errors on many and various problems, which is annoying. Well, after 11+ incorrect submissions, I learned I had it right all along except for that idiot rounding error. How annoying! Yet, strangely gratifying as well.
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"
Yousuf Shetu
New poster
Posts: 5
Joined: Fri May 07, 2004 7:00 pm
Location: London
Contact:

Compile Error if I use Java in problem 143

Post by Yousuf Shetu »

[/java]
//@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: 45460CH 136 Java "Ugly Numbers" */

class UglyNumbers
{
public static void main(String args[])
{
int dummy=0,count=0,number=1;

for(int i=1;;i++)
{
number = i;
dummy = number;
do
{
if((number%2 != 0)&&(number%3 != 0)&&(number%5 != 0))
break;

if(number%2 == 0)
number = number/2;
else if(number%3 == 0)
number = number/3;
else if(number%5 == 0)
number = number/5;
}while(number != 1);

if(number == 1)
count++;

if(count == 1500)
{
System.out.println("The 1500'th ugly number is <" +dummy +">");
break;
}
}
}
}
//@END_OF_SOURCE_CODE :cry: :cry:
yusufshetu
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Re: Compile Error if I use Java in problem 143

Post by chunyi81 »

Yousuf Shetu wrote:[java]
//@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: 45460CH 136 Java "Ugly Numbers" */

class UglyNumbers
{
public static void main(String args[])
{
int dummy=0,count=0,number=1;

for(int i=1;;i++)
{
number = i;
dummy = number;
do
{
if((number%2 != 0)&&(number%3 != 0)&&(number%5 != 0))
break;

if(number%2 == 0)
number = number/2;
else if(number%3 == 0)
number = number/3;
else if(number%5 == 0)
number = number/5;
}while(number != 1);

if(number == 1)
count++;

if(count == 1500)
{
System.out.println("The 1500'th ugly number is <" +dummy +">");
break;
}
}
}
}
//@END_OF_SOURCE_CODE [/java]
:cry: :cry:
Are you referring to problem 136 ugly numbers? Please quote the correct problem number. Please also read the description of the output format in the problem carefully. Your output format is wrong. Remove the // before you sbumit the program and your program should run fine. I have also seen your program for problem 100. Remove the // there as well before you submit. However, you will definitely get WA for problem 100 after you remove the //, because of your program output. Read the output description very carefully please.
CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am

143 Orchard Trees WA //PLEASE HELP ME

Post by CC »

I got a programme of this prob. which has been ACed from other posts
and randomly generated 10000 testdata
then I got the output of the two programs(mine and that one)
there are only one difference between the two
but after I changed that program (change eps from 1e-9 to 1e-8 )
there are no difference at all.

but when I submit, I always got WA

I don't know why

and this is my src below
[cpp]#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

#define eps 0.00000001
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)

struct Point
{
int x,y;
};

Point tri[3];

int deal(int bg,int ed)
{
if(bg!=0) bg=(bg-1)/100+1;
else bg=1;
if(ed!=10000) ed/=100;
else ed=99;
return (ed-bg)+1;
}

int proc()
{
int ans=0,i,bg,ed;
if(tri[0].y==tri[1].y&&tri[1].y==tri[2].y&&tri[1].y<=9900&&tri[1].y>=100)
{
bg=min(tri[0].x,min(tri[1].x,tri[2].x));
ed=max(tri[0].x,max(tri[1].x,tri[2].x));
return deal(bg,ed);
}
if(tri[0].y<tri[1].y) swap(tri[0],tri[1]);
if(tri[0].y<tri[2].y) swap(tri[0],tri[2]);
if((tri[2].x-tri[0].x)*(tri[1].y-tri[0].y)-(tri[2].y-tri[0].y)*(tri[1].x-tri[0].x)>0)
swap(tri[1],tri[2]);
//tri[0] has the highest y
//and line tri[0]==>tri[1] is on the left side of line tri[0]==>tri[2]
if(tri[1].y>=tri[2].y)
{
if(tri[0].y!=10000) i=tri[0].y/100*100;
else i=9900;
for(;i>=tri[1].y&&i>0;i-=100)
{
if(tri[0].y==tri[1].y)
bg=tri[1].x,ed=tri[0].x;
else
{
if((tri[0].x-tri[1].x)*(tri[0].y-i)%(tri[0].y-tri[1].y)>=0)
bg=tri[0].x-(tri[0].x-tri[1].x)*(tri[0].y-i)/(tri[0].y-tri[1].y);
else
bg=tri[0].x-(tri[0].x-tri[1].x)*(tri[0].y-i)/(tri[0].y-tri[1].y)+1;
if((tri[0].x-tri[2].x)*(tri[0].y-i)%(tri[0].y-tri[2].y)<=0)
ed=tri[0].x-(tri[0].x-tri[2].x)*(tri[0].y-i)/(tri[0].y-tri[2].y);
else
ed=tri[0].x-(tri[0].x-tri[2].x)*(tri[0].y-i)/(tri[0].y-tri[2].y)-1;
}
ans+=deal(bg,ed);
}
for(;i>=tri[2].y&&i>0;i-=100)
{
if((tri[1].x-tri[2].x)*(tri[1].y-i)%(tri[1].y-tri[2].y)>=0)
bg=tri[1].x-(tri[1].x-tri[2].x)*(tri[1].y-i)/(tri[1].y-tri[2].y);
else
bg=tri[1].x-(tri[1].x-tri[2].x)*(tri[1].y-i)/(tri[1].y-tri[2].y)+1;
if((tri[0].x-tri[2].x)*(tri[0].y-i)%(tri[0].y-tri[2].y)<=0)
ed=tri[0].x-(tri[0].x-tri[2].x)*(tri[0].y-i)/(tri[0].y-tri[2].y);
else
ed=tri[0].x-(tri[0].x-tri[2].x)*(tri[0].y-i)/(tri[0].y-tri[2].y)-1;
ans+=deal(bg,ed);
}
}
else//tri[0].y >=tri[2].y > tri[1].y
{
if(tri[0].y!=10000) i=tri[0].y/100*100;
else i=9900;
for(;i>=tri[2].y&&i>0;i-=100)
{
if((tri[0].x-tri[1].x)*(tri[0].y-i)%(tri[0].y-tri[1].y)>=0)
bg=tri[0].x-(tri[0].x-tri[1].x)*(tri[0].y-i)/(tri[0].y-tri[1].y);
else
bg=tri[0].x-(tri[0].x-tri[1].x)*(tri[0].y-i)/(tri[0].y-tri[1].y)+1;
if(tri[0].y==tri[2].y)
ed=tri[2].x;
else
{
if((tri[0].x-tri[2].x)*(tri[0].y-i)%(tri[0].y-tri[2].y)<=0)
ed=tri[0].x-(tri[0].x-tri[2].x)*(tri[0].y-i)/(tri[0].y-tri[2].y);
else
ed=tri[0].x-(tri[0].x-tri[2].x)*(tri[0].y-i)/(tri[0].y-tri[2].y)-1;
}
ans+=deal(bg,ed);
}
for(;i>=tri[1].y&&i>0;i-=100)
{
if((tri[0].x-tri[1].x)*(tri[0].y-i)%(tri[0].y-tri[1].y)>=0)
bg=tri[0].x-(tri[0].x-tri[1].x)*(tri[0].y-i)/(tri[0].y-tri[1].y);
else
bg=tri[0].x-(tri[0].x-tri[1].x)*(tri[0].y-i)/(tri[0].y-tri[1].y)+1;
if((tri[2].x-tri[1].x)*(tri[1].y-i)%(tri[2].y-tri[1].y)<=0)
ed=tri[1].x-(tri[1].x-tri[2].x)*(tri[1].y-i)/(tri[1].y-tri[2].y);
else
ed=tri[1].x-(tri[1].x-tri[2].x)*(tri[1].y-i)/(tri[1].y-tri[2].y)-1;
ans+=deal(bg,ed);
}
}
return ans;
}

int main()
{
// freopen("d:\\test.in","r",stdin);
// freopen("d:\\test.out","w",stdout);
double a1,b1,a2,b2,a3,b3;
while(1)
{
scanf("%lf %lf %lf %lf %lf %lf",&a1,&b1,&a2,&b2,&a3,&b3);
if(a1<eps&&a2<eps&&a3<eps) return 0;
a1+=eps,b1+=eps,a2+=eps,b2+=eps,a3+=eps,b3+=eps;
tri[0].x=(int)(a1*100),tri[0].y=(int)(b1*100);
tri[1].x=(int)(a2*100),tri[1].y=(int)(b2*100);
tri[2].x=(int)(a3*100),tri[2].y=(int)(b3*100);
printf("%4d\n",proc());
}
return 0;
}
[/cpp]

and this is the src I got from other posts
[cpp]
#include<iostream>
#include<math.h>

using namespace std;

const double esp=1e-8;

double tri[3][2];
int stx,sty,edx,edy;

double min(const double x1,const double x2)
{
return x1-x2<esp ? x1 : x2;
}

double max(const double x1,const double x2)
{
return x1-x2>-esp ? x1 : x2;
}

double multi(const double x0,const double y0,const double x1,const double y1,const double x2,const double y2)
{
return (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
}

int inside(int x,int y)
{
int i,i1,i11;
double flag1,flag2;
for(i=0;i<3;i++)
{
i1=(i==2 ? 0 : i+1);
i11=(i1==2 ? 0 : i1+1);
flag1=multi(tri[0],tri[1],tri[i1][0],tri[i1][1],tri[i11][0],tri[i11][1]);
flag2=multi(tri[0],tri[1],tri[i1][0],tri[i1][1],x,y);
if(fabs(flag1)<esp)
{
if(fabs(flag2)<esp&&x-min(min(tri[0],tri[i1][0]),tri[i11][0])>-esp&&x-max(max(tri[0],tri[i1][0]),tri[i11][0])<esp&&
y-min(min(tri[1],tri[i1][1]),tri[i11][1])>-esp&&y-max(max(tri[1],tri[i1][1]),tri[i11][1])<esp)
return 1;
return 0;
}else if(flag1*flag2<-esp)
return 0;
}
return 1;
}

int judge()
{
int i,j;
int res=0;
for(i=stx;i<=edx;i++)
{
for(j=sty;j<=edy;j++)
{
if(inside(i,j))
{
res++;
// cout<<i<<' '<<j<<endl;
}
}
}

return res;
}

int main()
{

int i,j,k;
int cinish=0;
int res;
int special;
double temp;
while(1)
{
cinish=1;
stx=sty=edx=edy=-1;
special=0;
for(i=0;i<3;i++)
{
for(j=0;j<2;j++)
{
cin>>tri[j];
if(fabs(tri[j])>esp)
cinish=0;
}
for(k=0;k<i;k++)
{
if(fabs(tri[i][0]-tri[k][0])<esp&&fabs(tri[i][1]-tri[k][1])<esp)
{
special++;
break;
}
}
if(stx<0||tri[i][0]-stx<esp)
{
stx=(int)(tri[i][0]-1);
if(stx<=0)
stx=1;
}
if(edx<0||tri[i][0]-edx>-esp)
{
edx=(int)(tri[i][0]+1);
if(edx>=100)
edx=99;
}
if(sty<0||tri[i][1]-sty<esp)
{
sty=(int)(tri[i][1]-1);
if(sty<=0)
sty=1;
}
if(edy<0||tri[i][1]-edy>-esp)
{
edy=(int)(tri[i][1]+1);
if(edy>=100)
edy=99;
}
}
if(cinish)
break;
if(special==2)
{
if(tri[0][0]>esp&&tri[0][0]-100<-esp&&tri[0][1]>esp&&tri[0][1]-100<-esp&&fabs(tri[0][0]-((int)tri[0][0]))<esp&&fabs(tri[0][1]-((int)tri[0][1]))<esp)
res=1;
else
res=0;
}else{
if(special==1&&fabs(tri[0][0]-tri[1][0])<esp&&fabs(tri[0][1]-tri[1][1])<esp)
{
temp=tri[1][0];
tri[1][0]=tri[2][0];
tri[2][0]=temp;
temp=tri[1][1];
tri[1][1]=tri[2][1];
tri[2][1]=temp;
}
res=judge();
}
cout.fill(' ');
cout.width(4);
cout<<res<<endl;
}
return 1;
}
[/cpp]
CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am

Post by CC »

just a few minutes ago, I generate another testdata
and there are 1M testcases

I got another src which has been ACed
[cpp]
#include "stdio.h"
#include "math.h"

double area(double a, double b, double c, double d, double e, double f)
{
return fabs(a*f+c*b+e*d-c*f-e*b-a*d);
}

void main()
{
freopen("d:\\test.in","r",stdin);
freopen("d:\\test2.out","w",stdout);
double a,b,c,d,e,f,s,t,u,v;
int i,j,k;
bool last;

while (1) {
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
if (a==0.0 && b==0.0 && c==0.0 && d==0.0 && e==0.0 && f==0.0) break;
k=0;
if (a>c) {
s=c;
t=a;
} else {
s=a;
t=c;
}
if (s>e) s=e;
if (t<e) t=e;
if (b>d) {
u=d;
v=b;
} else {
u=b;
v=d;
}
if (u>f) u=f;
if (v<f) v=f;
for (i=1;i<100;i++) {
if (i<s || i>t) continue;
last=false;
for (j=1;j<100;j++) {
if (j<u || j>v) continue;
if (fabs(area(a,b,c,d,i,j)+area(a,b,e,f,i,j)+area(e,f,c,d,i,j)-area(a,b,c,d,e,f))<1E-9) {
k++;
last=true;
} else if (last) break;
}
}
printf("%4d\n",k);
}
}

[/cpp]

and there are no difference between the two output

can judge give me the data I didn't pass?
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

Ha.
I have submited my code for this problem so many times but I got just wrong answer I test my code with an accepted code "click xx code" and in 100000 testcase I found just 1 diffrence
in this test case:
71.67 88.3 45.02 49.09 98.49 0.1
in this testcase I found 1701 point inside but accepted code found 1700
and so I found an EXTAR point and this point is
(97,5) that is in polygon and we should consider it!!!
so I think judge data for this problem is incorrect!!!.

this is my code:

[cpp]
I got accepted;)
[/cpp]
and I am now confused that this is my problem or this is judge problem?
please help me.
Last edited by Moha on Thu Feb 24, 2005 6:16 am, edited 1 time in total.
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

It`s unbelievable i have removed these lines
[cpp]if (minx<1)
minx=1;
if (miny<1)
miny=1;
if (maxx>99)
maxx=99;
if (maxy>99)
maxy=99;
[/cpp]
from my code , search entire space 100*100 but skip points according to max and min and got accepted! just in 2.47 sec. after many submission!!
Stas
New poster
Posts: 5
Joined: Sat Jul 03, 2004 5:15 pm
Location: Kyrgyzstan
Contact:

rounding errors

Post by Stas »

Try to change 'double' to 'long double'.
First I soved this problem on Pascal, but got wa.
Then I have translated to cpp and got AC.
tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

143 WA, give me I/O

Post by tan_Yui »

Hello, I'm confused at WA several times.
I read past posts of this board and used those sets of input.
It seems correct, but judge said WA....

Could anyone check following output ?
And if you have, please give me some I/O or advices.

Input :

Code: Select all

1.5 1.5 1.5 6.8 6.8 1.5
10.7 6.9 8.5 1.5 14.5 1.5
1 2 3 5 6 9
1 1 2 2 3 3
5 4 3.2 3.6 1.0 0.6
1.2 1.1 1.1 2.2 2.2 5.5
10.3 6.2 6.63 2.36 3.21 3.32
0.0 0.0 100.0 100.0 100.0 0.0
0.0 0.0 3.0 3.0 3.0 0.0
71.67 88.3 45.02 49.09 98.49 0.1
0 0 100 0 0 100
0.1 0.1 0.9 100 0.7 80
1 1 5 5 100 100
0 0 2.5 0.5 4 0.7
1 1 3 2 2 3
1 1 5 1 5 5
0.99999 0.99999 1.00001 0.99999 0.99999 1.00001
0 0 0 0 100 0
50.00 0.00 50.00 50.00 50.00 100.00
50.00 50.00 50.00 50.00 50.00 50.00
1 1 1 1 1 1
1 1 1 1 1.1 1.1
1 1 1 5 1 10
1 1 1 4 2 4
1 1 1 4 4 1
1 1 1 2 1 1
0 0 0 2 2 0
98 98 100 98 98 100
0 0 0 5 0.5 0
3.01 3.01 3.01 3.99 3.99 3.01
1 2 3 5 6 9
1 1 2 2 3 3
5 4 3.2 3.6 1.0 0.6 1.2
1.1 1.1 2.2 2.2 5.5 10.3
6.2 6.63 2.36 3.21 3.32
0.5 0.5 1.5 1.5 0.5 1.5
0 50 50 50 100 50
1 50 5 50 10 50
0 0 50 50 100 100
0 0 50 50 100 99
100 100 100 100 100 100
0 0 0 50 0 100
99.00001 99.00001 99.99999 99.99999 99.99999 99.99999
0 0 50 50 100 0
0 0  0 0  0 0
My output :

Code: Select all

  15
  17
   3
   3
   2
   0
  10
4950
   6
1700
4950
   0
  99
   0
   4
  15
   1
   0
  99
   1
   1
   1
  10
   5
  10
   2
   1
   4
   0
   0
   3
   3
   2
   0
  10
   1
  99
  10
  99
  50
   0
   0
   0
2500
Thank you.
teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni »

Code: Select all

71.67 88.3 45.02 49.09 98.49 0.1  ;;line 10
My output:

Code: Select all

1701
tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui »

Hi teni_teni, thank you for your reply :D
I couldn't find any bugs in my code, so I'll try to change the precision.

Now, I'm out of my home town.
After return to home, I'll report result of judgement into this board.

Best regards.
Post Reply

Return to “Volume 1 (100-199)”