143 - Orchard Trees

[tan_Yui]

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]

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]

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]

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

[yolongyi]

I just change double to long double..

[Joth]

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]

My accepted code returns...

Code: Select all

  50
   1

Hope it helps.

[Joth]

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]

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.

[andysoft]

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;
}

[tgoulart]

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

http://online-judge.uva.es/board/viewtopic.php?t=7805

[Moha]

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

[tgoulart]

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.

[andysoft]

thanks a lot People, I will try to fix it as you said.

[Moha]

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.