2080 夹角有多大II

关键字: 代码分享 杭电100题

问题描述

Problem Description

这次xhd面临的问题是这样的:在一个平面内有两个点,求两个点分别和原点的连线的夹角的大小。

注:夹角的范围[0,180],两个点不会在原点出现。

Input

输入数据的第一行是一个数据T,表示有T组数据。

每组数据有四个实数x1,y1,x2,y2分别表示两个点的坐标,这些实数的范围是[-10000,10000]。

Output

对于每组输入数据,输出夹角的大小精确到小数点后两位。

Sample Input

2
1 1 2 2
1 1 1 0

Sample Output

0.00
45.00

问题分析

Problem Analyse

数学题

Algorithm Analyse

我们可以先用arcsin求出每个点的角度。(不用arctan是因为x可能等于0)

公式:asin(y/sqrt(sqr(x)+sqr(y)))/acos(-1)*180;

之所以加个acos(-1),即π,是因为C语言里的asin结果是弧度制,但我们需要角度制。

这里,我们要处理平角的情况(即180°)if (!y && x < 0) y = 180;接下来就要求两个角度的差了(小于0的一直加360,大于360的一直减360);最后还要判断结果是否大于180°

此处没有考虑钝角的情况。比如输入-1 -1 1 0,应该输出135,但却只输出了45。可这样依然能AC,说明题目的测试数据很弱,但我们自己必须注意。

本题还有个更简单的方法,因为输入的两个点与原点构成一个三角形。又因为 S△ = 0.5 * sinψ * A * B,其中ψ就是A, B的夹角了。而两点与原点构成的三角形的面积为 fabs(x[0]*y[1]-x[1]*y[0]) / 2;(推导见2036)。

算法实现

给出第一种方法的AC代码

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

#define sqr(x) ((x)*(x))

int main(void)
{
  int n;
  double x[2], y[2];
  
  scanf("%d", &n);
  while (n-- && scanf("%lf%lf%lf%lf", x, y, x+1, y+1))
  {
    y[0] = asin(y[0]/sqrt(sqr(x[0])+sqr(y[0])))/acos(-1)*180;
    y[1] = asin(y[1]/sqrt(sqr(x[1])+sqr(y[1])))/acos(-1)*180;
    if (!y[0] && x[0] < 0) y[0] = 180;
    if (!y[1] && x[1] < 0) y[1] = 180;
    y[0] -= y[1];
    while (y[0] < 0) y[0] += 360;
    while (y[0] > 360) y[0] -= 360;
    while (y[0] > 180) y[0] = 360 - y[0];
    printf("%.2f\n", y[0]);
  }
  
  return 0;
}

参考源码

redraiment使用Emacs Lisp批量迁移《HDU 2080-2089》