I changed the precision to 'long double' or 'float' from 'double', but my code couldn't output the value '1701'.tan_Yui wrote:I couldn't find any bugs in my code, so I'll try to change the precision.
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);
}
}
Code: Select all
1 1 50 1 100 1.01
1 1 100 1.01 1 1.01
0 0 0 0 0 0Code: Select all
50
1Code: Select all
50 1 100 .99999 0 .99999
50 1 100 1.00001 0 1.00001
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;
}