[已解决]平面几何问题之三角形的整数点

乐乐学编程

求在一个已知三个顶点的三角形内有多少个横坐标与纵坐标都是整数的点

最佳答案

月排行榜 / 总排行榜

风过无痕1989

2020-11-28 19:32:41

#include <stdio.h>
#include<math.h>

double S_tri(double ax, double ay, double bx, double by, double cx, double cy)
{
        double S;
        S = 0.5 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
        if (S >= 0)
                return S;
        else
                return (-1.0 * S);
}


void main()

{
        int x, y, count = 0;
        double max1, min1, max2, min2;
        double S, S1, S2, S3, ax, ay, bx, by, cx, cy;
        scanf("%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy);
        S = S_tri(ax, ay, bx, by, cx, cy);
        max1 = ax;
        min1 = ax;
        if (max1 < bx)
                max1 = bx;
        if (max1 < cx)
                max1 = cx;
        if (min1 > bx)
                min1 = bx;
        if (min1 > cx)
                min1 = cx;
        max2 = ay;
        min2 = ay;
        if (max2 < by)
                max2 = by;
        if (max2 < cy)
                max2 = cy;
        if (min2 > by)
                min2 = by;
        if (min2 > cy)
                min2 = cy;

        for (x = min1;x <= max1;x++)
        {
                for (y = min2;y <= max2;y++)
                {
                        S1 = S_tri(x, y, bx, by, cx, cy);
                        S2 = S_tri(ax, ay, x, y, cx, cy);
                        S3 = S_tri(ax, ay, bx, by, x, y);
                        if (fabs(S - (S1 + S2 + S3)) < 0.000001)
                                count++;
                }
        }
        printf("在给定三点的三角形内有整数点 %d 个\n", count);
}

跳转到最佳答案楼层

风过无痕1989

#include <stdio.h>
#include<math.h>

double S_tri(double ax, double ay, double bx, double by, double cx, double cy)
{
        double S;
        S = 0.5 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
        if (S >= 0)
                return S;
        else
                return (-1.0 * S);
}


void main()

{
        int x, y, count = 0;
        double max1, min1, max2, min2;
        double S, S1, S2, S3, ax, ay, bx, by, cx, cy;
        scanf("%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy);
        S = S_tri(ax, ay, bx, by, cx, cy);
        max1 = ax;
        min1 = ax;
        if (max1 < bx)
                max1 = bx;
        if (max1 < cx)
                max1 = cx;
        if (min1 > bx)
                min1 = bx;
        if (min1 > cx)
                min1 = cx;
        max2 = ay;
        min2 = ay;
        if (max2 < by)
                max2 = by;
        if (max2 < cy)
                max2 = cy;
        if (min2 > by)
                min2 = by;
        if (min2 > cy)
                min2 = cy;

        for (x = min1;x <= max1;x++)
        {
                for (y = min2;y <= max2;y++)
                {
                        S1 = S_tri(x, y, bx, by, cx, cy);
                        S2 = S_tri(ax, ay, x, y, cx, cy);
                        S3 = S_tri(ax, ay, bx, by, x, y);
                        if (fabs(S - (S1 + S2 + S3)) < 0.000001)
                                count++;
                }
        }
        printf("在给定三点的三角形内有整数点 %d 个\n", count);
}

风过无痕1989

你的问题都具有挑战性，我回复你第一个问题，被审核了，此题目做完后，就没敢再发了

乐乐学编程

风过无痕1989 发表于 2020-11-28 19:39
你的问题都具有挑战性，我回复你第一个问题，被审核了，此题目做完后，就没敢再发了

多谢了！

风过无痕1989

乐乐学编程 发表于 2020-11-28 21:46
多谢了！

客气了