2018年全国多校算法寒假训练营练习比赛（第三场） I.三角形（计算几何）

链接：https://www.nowcoder.net/acm/contest/75/I
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给你一个三角形的顶点A,B,C的坐标（坐标都为整数），请求出三角形的面积，三角形内的点的个数以及边AB、BC和AC边上的点的个数（不包括顶点ABC）
2018年全国多校算法寒假训练营练习比赛（第三场） I.三角形（计算几何）

输入描述:

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

输出描述:

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

示例1

输入

输出

2.0 0 1 1 1
4.5 1 2 2 2

说明

第一组图一，第二组图二


分析：  
三角形面积公式S=1/2absinC 可用向量叉乘得出其面积

对于边上的点：

把每条边当做左开右闭的区间以避免重复，一条左开右闭的线段(x1,y1)->(x2,y2)上的格点数为：

　gcd(|x2-x1|,|y2-y1|)。

对于三角内的点,由皮克定理：

2018年全国多校算法寒假训练营练习比赛（第三场） I.三角形（计算几何）

S为三角形面积，n为三角形内部的点，s为三角形边上的点

代码如下：

#include<iostream> 
#include<cstring> 
#include<cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
struct Point
{
  LL x;
  LL y;
  Point(LL a=0,LL b=0):x(a),y(b){
  }
  void init()
  {
      cin>>x;
      cin>>y;
  }
  Point operator -(Point a)
  {
      return Point(x-a.x,y-a.y);
  }
}P[5];
double S(Point a,Point b)
{
  return fabs(a.x*b.y-a.y*b.x)/2;
}
double so(Point a)
{
    LL p=fabs(a.x),q=fabs(a.y);
    return __gcd(p,q);
}
int main()
{
    LL ab,bc,ac,ans;
    while(cin>>P[1].x)
    {
       if(P[1].x==-1)break;
       cin>>P[1].y;
       for(int i=2;i<=3;i++)
       P[i].init();
      double SS;
      SS=S(P[2]-P[1],P[3]-P[1]);
      ab=so(P[1]-P[2]);
      bc=so(P[2]-P[3]);
      ac=so(P[1]-P[3]);
      ans=SS-(ab+bc+ac)/2+1;
      printf("%.1f %lld %lld %lld %lld
",SS,ans,ab-1,bc-1,ac-1);
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛（第三场） I.三角形 （计算几何）

题目描述

输入描述:

输出描述:

输入

输出

说明

相关推荐

2018年全国多校算法寒假训练营练习比赛（第三场） I.三角形（计算几何）