143 - Orchard Trees

[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]

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]

[junbin]

Your output is correct.

[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]

[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.

[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

[chunyi81]

[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]

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]

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]

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]

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.

[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]

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]

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]

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]

Hi teni_teni, thank you for your reply
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.