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

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

Post by tan_Yui » Fri Apr 01, 2005 3:30 pm

tan_Yui wrote:I couldn't find any bugs in my code, so I'll try to change the precision.
I changed the precision to 'long double' or 'float' from 'double', but my code couldn't output the value '1701'.
The reason for WA of my code might be in other place not in the precision.

My code has become complex...., so I'll rewrite whole of code. :(

Thanks for your help.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

143 - Orchard Trees

Post by Quantris » Mon Apr 25, 2005 9:51 pm

I know there are already a couple of posts regarding this, my program gives the correct output for the input I could find.

However I've gotten *tons* of WA's on this problem, I increased my precision to a very high degree and tested with all sorts of boundary cases, so I begin to wonder if the judge program is not precise enough for one of its cases?

I was just curious about what anyone who got AC on this problem had to do with their precision (did you increase it, or decrease it) or if there was something misleading in the problem statement (do we really only consider points from 1 to 99)?

Thanks for any help you can provide :)

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

143 Need help!

Post by AndyGee » Tue Aug 30, 2005 9:05 pm

Why WA? Please help me... i mad with this problem...

Code: Select all

/* ACM Problem Set */

/* Problem 143 */
/* Orchard Trees */ 

#include <cstdio>
#include <math.h>
#include <stdlib.h>
#define min(a,b) a < b ? a : b
#define max(a,b) a > b ? a : b
#define less0(a) a < 1 ? 1 : a
#define most100(a) a > 99 ? 99 : a
#define epsilon 0.00000001
using namespace std; 

bool IsIntersectWithHorizont (int H, long double x1, long double y1, long double x2, long double y2)
{
   if (y1 == y2) return false;
   long double X = x2 - ((y2 - (long double)H) * (x2 - x1) / (y2 - y1));
   if (((X >= x1) && (X <= x2)) || ((X <= x1) && (X >= x2))) return true;
   else return false;
}

long double FindIntersectWithHorizont (int H, long double x1, long double y1, long double x2, long double y2)
{
   return x2 - ((y2 - (long double)H) * (x2 - x1) / (y2 - y1));
}

int CountPointsOnLine (int H, long double x1, long double y1, long double x2, long double y2, long double x3, long double y3)
{
   long double LeftPoint = 101, RightPoint = 0;
   if (IsIntersectWithHorizont(H, x1, y1, x2, y2))
   {
      LeftPoint = min (LeftPoint, FindIntersectWithHorizont(H, x1, y1, x2, y2));
      RightPoint = max (RightPoint, FindIntersectWithHorizont(H, x1, y1, x2, y2));
   }
   if (IsIntersectWithHorizont(H, x1, y1, x3, y3))
   {
      LeftPoint = min (LeftPoint, FindIntersectWithHorizont(H, x1, y1, x3, y3));
      RightPoint = max (RightPoint, FindIntersectWithHorizont(H, x1, y1, x3, y3));
   }
   if (IsIntersectWithHorizont(H, x3, y3, x2, y2))
   {
      LeftPoint = min (LeftPoint, FindIntersectWithHorizont(H, x3, y3, x2, y2));
      RightPoint = max (RightPoint, FindIntersectWithHorizont(H, x3, y3, x2, y2));
   }
   if (RightPoint > 99) RightPoint = 99.0;
   if (RightPoint < 1) return 0;
   if (LeftPoint < 1) LeftPoint = 1.0;
   if (LeftPoint > 99) return 0;
   return (int)(float(RightPoint + epsilon) - ceil(LeftPoint - epsilon) + 1);
}

int main()
{
   long double x1, x2, x3, y1, y2, y3;
   while (scanf("%llf %llf %llf %llf %llf %llf\n", &x1, &y1, &x2, &y2, &x3, &y3) == 6)
   {
      if (!(x1 || x2 || x3 || y1 || y2 || y3)) break;
      int ans = 0;
      if ((y1 == y2) && (y2 == y3))
      {
         if ((int)float(y1) == (int)ceil(y1)) ans = (most100(less0((int)float(max(x1,(max(x2,x3))) + epsilon))) - most100(less0((int)ceil(min(x1,(min(x2,x3))) - epsilon))));
         if ((y1 == 100) || (y1 == 0)) ans = 0;
      }
      else
      {
         int B = most100(less0((int)ceil(min(y1,(min(y2,y3))) - epsilon)));
         int T = most100(less0((int)float(max(y1,(max(y2,y3))) + epsilon)));
         for (int y = B; y <= T; y++)
         {
            ans += CountPointsOnLine(y, x1, y1, x2, y2, x3, y3);
         }
      }
      printf("%4d\n", ans);
   }
}

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

143 Ochard Trees WA......help,,,,

Post by yolongyi » Wed Feb 01, 2006 9:46 pm

I'm getting WA .....
this makes me crazy...
My code do correctly in some test cases that are in this board...
but getting WA...
what is problem...
can anyone talk to me??
and is there a special cases??
help me.........


Code is deleted after I have accepted..
Last edited by yolongyi on Fri Feb 03, 2006 5:02 pm, edited 1 time in total.
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

I accepted!!

Post by yolongyi » Fri Feb 03, 2006 5:01 pm

I just change double to long double..
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

Joth
New poster
Posts: 11
Joined: Sat Mar 10, 2007 8:29 pm

Post by Joth » Fri Apr 13, 2007 6:27 am

can anyone with an AC on this problem tell me what they get with this data?

Code: Select all

1 1 50 1 100 1.01
1 1 100 1.01 1 1.01
0 0 0 0 0 0
thanks all!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Apr 13, 2007 10:08 am

My accepted code returns...

Code: Select all

  50
   1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Joth
New poster
Posts: 11
Joined: Sat Mar 10, 2007 8:29 pm

Post by Joth » Fri Apr 13, 2007 8:06 pm

thanks Jan! i get the same...
could you give me your results for

Code: Select all

50 1 100 .99999 0 .99999
50 1 100 1.00001 0 1.00001
does anyone know if there is a limit to the amount of precision on the input? I believe at one point in the problem the range is given as 0.0 to 100.0 and later as 0.00 to 100.00... does this mean input is limited to the hundredths position?
thanks again!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Apr 13, 2007 8:38 pm

I think the judge input is not that dirty. My code assumes that there is no number with more than 2 digits after the decimal point.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Wed Jun 27, 2007 4:02 pm

I search only from min x to max x and from min y to max y, then calculate the area, but is still is TLE, look at my code:

Code: Select all

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <math.h>

using namespace std;

long double xx1,yy1,xx2,yy2,xx3,yy3,eps=0.00001,s;

long double abs2(long double n) {
       if (n<0)
          return -n;
       else
           return n;
}

long double d(long double x1,long double y1,long double x2, long double y2) {
       return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

long double f(long double x1, long double y1, long double x2, long double y2, long double x3, long double y3) {
       long double a = d(x1,y1,x2,y2), b = d(x1,y1,x3,y3), c = d(x2,y2,x3,y3),p=(a+b+c)/2;       
       return sqrt(p*(p-a)*(p-b)*(p-c));
}

bool inside (int x, int y) {
     long double           
           s1 = f(x,y,xx1,yy1,xx2,yy2),
           s2 = f(x,y,xx2,yy2,xx3,yy3),
           s3 = f(x,y,xx1,yy1,xx3,yy3);
           
     return (abs2(s1+s2+s3-s) < eps);

}

long double min (long double a,long double b) {
       return a<b?a:b;
}
long double max(long double a,long double b) {
       return a>b?a:b;
}
long double min3 (long double a, long double b, long double c) {
       return min(a,min(b,c));     
}
long double max3 (long double a, long double b, long double c) {
       return max(a,max(b,c));       
}

int main(int argc, char *argv[]) {
    
    long int x,y,ans;
    
    cin >> xx1 >> yy1 >> xx2 >> yy2 >> xx3 >> yy3;
    
    while (!((xx1==0)&&(xx2==0)&&(yy1==0)&&(yy2==0)&&(xx3==0)&&(yy3==0))) {
          
          s = f(xx1,yy1,xx2,yy2,xx3,yy3);
    
    ans = 0;
    int xxx=int (floor(min3(xx1,xx2,xx3)));
    if (xxx<1) xxx=1;
    int xxxm=int (ceil(max3(xx1,xx2,xx3)));
    if (xxxm>99) xxxm=99;
    int yyy=int(floor(min3(yy1,yy2,yy3)));
    if (yyy<1) yyy=1;
    int yyym=int(ceil(max3(yy1,yy2,yy3)));
    if (yyym>99) yyym=99;
        
    
    for (x=xxx;x<=xxxm;x++)
        for (y=yyy;y<=yyym;y++) 
            if (inside (x,y)) ans++; 
            
    printf ("%4d\n",ans);
    cin >> xx1 >> yy1 >> xx2 >> yy2 >> xx3 >> yy3;
    
    }

    return EXIT_SUCCESS;
}

Now I lay me down to sleep...
my profile

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Wed Jun 27, 2007 8:51 pm

Besides the TLE, your code gives wrong answer for the data in this thread:

http://online-judge.uva.es/board/viewtopic.php?t=7805
Thiago Sonego Goulart - UFMG/Brazil

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Thu Jun 28, 2007 9:54 pm

Obviously a simple brute force method does not provide the response in the limited time. Try to improve your code a bit!

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Thu Jun 28, 2007 10:11 pm

Actually, it is possible to get AC with a brute force method, but you must use a simpler way to see if the point is in the triangle. This one above is too slow.
Thiago Sonego Goulart - UFMG/Brazil

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Thu Jun 28, 2007 10:20 pm

thanks a lot People, I will try to fix it as you said.
Now I lay me down to sleep...
my profile

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Fri Jun 29, 2007 5:32 pm

A simple improvement which is applicable to your code is try not to use sqrt function. Also you can find out whether the point is inside or on the triangle or not. I know you can find its formula with a little knowledge of Euclidean geometry.

Spoiler: use the area for the determination.

Post Reply

Return to “Volume 1 (100-199)”