题目

{% fold 点击显/隐题目 %}

Apple is Taotao's favourite fruit. In his backyard, there are three apple trees with coordinates $(x_1, y_1)$, $(x_2, y_2)$, and $(x_3, y_3)$. Now Taotao is planning to plant a new one, but he is not willing to take these trees too close. He believes that the new apple tree should be outside the circle which the three apple trees that already exist is on. Taotao picked a potential position $(x,y)$ of the new tree. Could you tell him if it is outside the circle or not?

The first line contains an integer $T$, indicating that there are $T(T \leq 30)$ cases. In the first line of each case, there are eight integers $x_1, y_1, x_2, y_2, x_3,y_3,x,y$, as described above. The absolute values of integers in input are less than or equal to $1,000,000,000,000$. It is guaranteed that, any three of the four positions do not lie on a straight line.

For each case, output "Accepted" if the position is outside the circle, or "Rejected" if the position is on or inside the circle.

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

Accepted Rejected Rejected

{% endfold %}

题解

求4个点中的第四个点是否在前三个点的外接圆外

大体思路就是中位线交点求圆心,比较距离
数据高达 1e12 因此需要用到高精度计算

然而这题会卡Java的BigDecimal(黑科技数据)

尽可能少用除法
根据公式可以发现可能会影响精度的地方如下:

求中点时除以2
求交点时除法
求距离时平方根

因为我们只需要比较最后的大小关系,因此比较距离可以变为比较距离的平方
同时,把求交点时的除法提取出来,可以变成把除数乘到点上
这样只需要除以2就行了,这样就不会被数据卡了

~~这题一点意思都没有,虽然比赛的时候没过~~

代码

{% fold 点击显/隐代码 %}```java Apple https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
import java.io.;
import java.util.;
import java.math.*;

class Point {
BigDecimal x, y;

public Point() {
}

public Point(BigDecimal _x, BigDecimal _y) {
    this.x = _x;
    this.y = _y;
}

}

class Segment {
Point a, b;

public Segment() {
}

public Segment(Point _a, Point _b) {
    this.a = _a;
    this.b = _b;
}

}

public class Main {
static Scanner cin;
static BigDecimal two;
static BigDecimal f1;

static Point read_point() {
    BigDecimal x = cin.nextBigDecimal();
    BigDecimal y = cin.nextBigDecimal();
    return new Point(x, y);
}

static Point pa(Point a, Point b) {
    return new Point(a.x.add(b.x), a.y.add(b.y));
}

static Point ps(Point a, Point b) {
    return new Point(a.x.subtract(b.x), a.y.subtract(b.y));
}

static Point getPoint(Point a, Point b) {
    Point p = pa(a, b);
    p.x = p.x.divide(two);
    p.y = p.y.divide(two);
    return p;
}

static Point fa(Point p) {
    return new Point(p.y.multiply(f1), p.x);
}

static Segment getSegment(Segment s) {
    Point mp = getPoint(s.a, s.b);
    Point vec = fa(ps(s.b, s.a));
    return new Segment(mp, pa(mp, vec));
}

static Point Seg_Seg(Segment L1, Segment L2, BigDecimal[] f) {
    BigDecimal a = L1.b.x.subtract(L1.a.x);
    BigDecimal b = L2.b.x.subtract(L2.a.x);
    BigDecimal c = L1.b.y.subtract(L1.a.y);
    BigDecimal d = L2.b.y.subtract(L2.a.y);
    f[0] = a.multiply(d).subtract(b.multiply(c));
    BigDecimal g = L2.b.x.subtract(L1.a.x);
    BigDecimal h = L2.b.y.subtract(L1.a.y);
    BigDecimal t = d.multiply(g).subtract(b.multiply(h));
    Point p = new Point(L1.a.x.add(t.multiply(a)), L1.a.y.add(t.multiply(c)));
    return p;
}

static BigDecimal distance(Point a, Point b) {
    Point p = ps(a, b);
    return p.x.multiply(p.x).add(p.y.multiply(p.y));
}

static void sprint(Segment s) {
    pprint(s.a, false);
    pprint(s.b, false);
    System.out.print("\n");
}

static void pprint(Point p, boolean f) {
    System.out.print("(");
    System.out.print(p.x);
    System.out.print(" ");
    System.out.print(p.y);
    System.out.print(")");
    if (f == true)
        System.out.print("\n");
}

public static void main(String[] args) {
    cin = new Scanner(new BufferedInputStream(System.in));
    two = BigDecimal.valueOf(2);
    f1 = BigDecimal.valueOf(-1);

    Point p[] = new Point[4];

    int T = cin.nextInt();
    for (int kase = 0; kase < T; ++kase) {
        for (int i = 0; i < 4; ++i) {
            p[i] = read_point();
        }
        Segment a = getSegment(new Segment(p[0], p[1]));
        Segment b = getSegment(new Segment(p[1], p[2]));

        BigDecimal[] f = { two };
        Point o = Seg_Seg(a, b, f);

        p[0].x = p[0].x.multiply(f[0]);
        p[0].y = p[0].y.multiply(f[0]);
        p[3].x = p[3].x.multiply(f[0]);
        p[3].y = p[3].y.multiply(f[0]);

        BigDecimal r = distance(p[0], o);
        BigDecimal dis = distance(p[3], o);

        //sprint(a);
        //sprint(b);
        // System.out.println(r);
        // pprint(o, true);
        // System.out.println(dis);

        if (dis.subtract(r).signum() > 0) {
            System.out.println("Accepted");
        } else {
            System.out.println("Rejected");
        }
    }
    cin.close();
}

}

{% endfold %}

HDU 6206.Apple

题目

题解

代码