题目102：文件中的三角形中有多少个内部包含原点？

欧拉计划

Triangle containment

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

题目：

在笛卡尔平面上随机取三个不同的点，其中 -1000 ≤ x, y ≤ 1000，会形成一个三角形。

考虑如下两个三角形：

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

可以证明三角形 ABC 包含原点在其内部，而三角形 XYZ 则不包含。
p102_triangles.txt (25.76 KB, 下载次数: 26)

2016-8-17 18:07 上传

点击文件名下载附件

包含一千个随机三角形，求其中有多少个三角形的内部包含原点。

注意：文件中的前两个三角形即为上述例子中的三角形。

jerryxjr1220

这题的思路是利用同向法求点是否包含在三角形内部：

                               
登录/注册后可看大图

假设点P位于三角形内，会有这样一个规律，当我们沿着ABCA的方向在三条边上行走时，你会发现点P始终位于边AB，BC和CA的右侧。我们就利用这一点，但是如何判断一个点在线段的左侧还是右侧呢？我们可以从另一个角度来思考，当选定线段AB时，点C位于AB的右侧，同理选定BC时，点A位于BC的右侧，最后选定CA时，点B位于CA的右侧，所以当选择某一条边时，我们只需验证点P与该边所对的点在同一侧即可。问题又来了，如何判断两个点在某条线段的同一侧呢？

两点p1(x1,y1),p2(x2,y2),判断点p(x,y)在线的左边还是右边：

Tmp = (y1 – y2) * x + (x2 – x1) * y + x1 * y2 – x2 * y1
Tmp > 0 在左侧
Tmp = 0 在线上
Tmp < 0 在右侧

所以，有了方法写程序就很简单了：

# -*- coding: utf-8 -*-
"""
Created on Sat Jan  7 09:41:55 2017

@author: Jerry Xu
"""

def tend(a,b,p):
    x1,y1 = a
    x2,y2 = b
    x, y  = p
    return (y1-y2)*x + (x2-x1)*y + x1*y2 -x2*y1
    
def judge(a,b,c):
    d1 = tend(a,b,(0,0))
    d2 = tend(b,c,(0,0))
    d3 = tend(c,a,(0,0))
    if (d1>0 and d2>0 and d3>0) or (d1<0 and d2<0 and d3<0): #我们只需判断是否同向即可，都左或者都右都可以。
        return True
    else:
        return False

c = 0
with open('p102_triangles.txt') as f:
    lines = f.readlines()
for line in lines:
    line = line.strip('\n').split(',')
    A = (int(line[0]),int(line[1]))
    B = (int(line[2]),int(line[3]))
    C = (int(line[4]),int(line[5]))
    if judge(A,B,C):
        c += 1
print (c)

输出：
228

芒果加黄桃

# encoding:utf-8
# 面积法
from time import time
from math import sqrt
P = (0, 0)
def calArea(A, B, C):
    a = sqrt((A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2)
    b = sqrt((A[0] - C[0]) ** 2 + (A[1] - C[1]) ** 2)
    c = sqrt((B[0] - C[0]) ** 2 + (B[1] - C[1]) ** 2)
    p = (a + b + c) / 2
    return sqrt(p * (p - a) * (p - b) * (p - c))
def isInTri(points):
    A, B, C = (points[0], points[1]), (points[2], points[3]), (points[4], points[5])
    area_ac = calArea(P, A, C)
    area_bc = calArea(P, B, C)
    area_ab = calArea(P, A, B)
    area_bac = calArea(A, B, C)
    if abs(area_ac + area_ab + area_bc - area_bac) < 0.00001:
        return True
def euler102():
    count = 0
    with open('p102_triangles.txt') as file:
        for line in file:
            points = [int(x) for x in line.replace('\n', '').split(',')]
            if isInTri(points):
                print(points)
                count += 1
    print(count)
if __name__ == '__main__':
    start = time() 
    euler102()
    print('cost %.6f sec' % (time() - start))

228
cost 0.058000 sec

芒果加黄桃

# encoding:utf-8
# 重心法
from time import time
class Vector2:
    def __init__(self, t):
        self.x = t[0]
        self.y = t[1]
    def minus(self, t):
        return Vector2((self.x - t.x, self.y - t.y))    
    def dot(self, t):
        return self.x * t.x + self.y * t.y
P = Vector2((0, 0))
def isInTri(A, B, C):
    v0 = C.minus(A)
    v1 = B.minus(A)
    v2 = P.minus(A)
    dot00 = v0.dot(v0)
    dot01 = v0.dot(v1)
    dot02 = v0.dot(v2)
    dot11 = v1.dot(v1)
    dot12 = v1.dot(v2)
    div = 1 / (dot00 * dot11 - dot01 * dot01)
    u = (dot11 * dot02 - dot01 * dot12) * div
    if u <= 0 or u >= 1:
        return False
    v = (dot00 * dot12 - dot01 * dot02) * div
    if v <= 0 or v >= 1:
        return False
    return u + v < 1
def euler102():
    count = 0
    with open('p102_triangles.txt') as file:
        for line in file:
            tmp = line.replace('\n', '').split(',')
            A = Vector2((int(tmp[0]), int(tmp[1])))
            B = Vector2((int(tmp[2]), int(tmp[3])))
            C = Vector2((int(tmp[4]), int(tmp[5])))
            if isInTri(A, B, C):
                print(tmp)
                count += 1
    print(count)
if __name__ == '__main__':
    start = time() 
    euler102()
    print('cost %.6f sec' % (time() - start))

debuggerzh

异端方法

                               
登录/注册后可看大图

guosl

利用内积的性质。

/*
答案：228
*/
#include <cstdio>

int main(void)
{
  errno_t err;
  FILE *fp = NULL;
  err = fopen_s(&fp, "p102_triangles.txt", "r");//打开文件
  if (err != 0)
  {
    printf_s("数据文件未打开\n");
    return 0;
  }
  int x[3], y[3];
  int nCount = 0;
  while (fscanf_s(fp, "%d,%d,%d,%d,%d,%d", &x[0], &y[0], &x[1], &y[1], &x[2], &y[2]) != EOF)
  {
    int d1 = x[0] * y[1] - x[1] * y[0];
    int d2 = x[1] * y[2] - x[2] * y[1];
    int d3= x[2] * y[0] - x[0] * y[2];
    if (d1 > 0 && d2 > 0 && d3 > 0 || d1 < 0 && d2 < 0 && d3 < 0)
      ++nCount;
  }
  fclose(fp);
  printf_s("%d\n", nCount);
  return 0;
}