列表

详情


NC15087. 三角形

描述

 

给你一个三角形的顶点A,B,C的坐标(坐标都为整数),请求出三角形的面积,三角形内的点的个数以及边AB、BC和AC边上的点的个数(不包括顶点ABC)

输入描述

多组输入
每组输入三行,每行两个整数
第一行顶点A的坐标Xa,Ya.
第二行顶点B的坐标Xb,Yb.
第三行顶点C的坐标Xc,Yc.
0<=X,Y<=1,000,000
输入-1结束输入

输出描述

每组输出一行,输出一个实数(保留一位小数),四个整数,分别代表三角形面积,三角形内的点的个数以及边AB、BC和AC边上的点的个数,每个数用空格隔开。

示例1

输入:

0 0
2 0
0 2
0 0
3 0
0 3
-1

输出:

2.0 0 1 1 1
4.5 1 2 2 2

说明:

第一组图一,第二组图二

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 404K, 提交时间: 2019-11-27 20:50:49

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long x1,y1,x2,y2,x3,y3;
    while(~scanf("%lld",&x1))
    {
        if(x1==-1)
        break;
        long long AB,AC,BC;
        cin>>y1>>x2>>y2>>x3>>y3;
        double s=(double)(abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2))/2.0;
        BC=__gcd(abs(x2-x3),abs(y2-y3))-1;
        AB=__gcd(abs(x2-x1),abs(y2-y1))-1;
        AC=__gcd(abs(x3-x1),abs(y3-y1))-1;
        long long n=s-(AB+AC+BC+3)/2.0+1;
        printf("%.1f %lld %lld %lld %lld\n",s,n,AB,BC,AC);
    }

}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 380K, 提交时间: 2020-02-29 18:34:56

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL gcd(LL a,LL b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int main()
{
	LL x1,y1,x2,y2,x3,y3;
	while(cin>>x1&&x1!=-1)
	{
		cin>>y1>>x2>>y2>>x3>>y3;
		double s=(double)(abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2))/2;
		LL ans1=gcd(abs(x1-x2),abs(y1-y2));
		LL ans2=gcd(abs(x1-x3),abs(y1-y3));
		LL ans3=gcd(abs(x2-x3),abs(y2-y3));
		LL ans=s-(ans1+ans2+ans3)/2+1;
		printf("%0.1f %lld %lld %lld %lld\n",s,ans,ans1-1,ans3-1,ans2-1);
	}
	return 0;
}

上一题