首页 > 试题广场 >

数三角形

[编程题]数三角形
  • 热度指数:5620 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出平面上的n个点,现在需要你求出,在这n个点里选3个点能构成一个三角形的方案有几种。



输入描述:
第一行包含一个正整数n,表示平面上有n个点(n <= 100)
第2行到第n + 1行,每行有两个整数,表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100,且保证所有坐标不同)


输出描述:
输出一个数,表示能构成三角形的方案数。
示例1

输入

4
0 0
0 1
1 0
1 1

输出

4

说明

4个点中任意选择3个都能构成三角形
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, cnt=0;
    scanf("%d", &n);
    int x[n], y[n];
    for(int i=0;i<n;i++)
        scanf("%d%d", &x[i], &y[i]);
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            for(int k=j+1;k<n;k++)
                if((x[k]-x[i])*(y[j]-y[i]) != (x[j]-x[i])*(y[k]-y[i]))
                    cnt++;
    printf("%d\n", cnt);
    return 0;
}

发表于 2020-11-12 01:12:41 回复(0)
import java.util.Scanner;

public class Main {

    static class Point {

        double x;
        double y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public double getX() {
            return x;
        }

        public void setX(double x) {
            this.x = x;
        }

        public double getY() {
            return y;
        }

        public void setY(double y) {
            this.y = y;
        }

    }

    static class Line {
        private Point point1;
        private Point point2;
        // 斜率
        private double slope;
        private double length;

        public Line(Point point1, Point point2) {
            this.point1 = point1;
            this.point2 = point2;
            this.slope = (point1.getY() - point2.getY()) / (point1.getX() - point2.getX());
            this.length = Math.sqrt(Math.pow(Math.abs(point1.getY() - point2.getY()), 2)
                    + Math.pow(Math.abs(point1.getX() - point2.getX()), 2));
        }

        public double getSlope() {
            return slope;
        }

        public boolean isParallel(Line line) {
            if (this.slope == line.getSlope())
                return true;
            return false;
        }

        public double getLength() {
            return length;
        }

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int len = sc.nextInt();
            Point[] ps = new Point[len];
            for (int i = 0; i < len; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                Point p = new Point(x, y);
                ps[i] = p;
            }
            int count = 0;
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j < len; j++) {
                    for (int k = j + 1; k < len; k++) {
                        if (isValid(ps[i], ps[j], ps[k])) {
                            count++;
                        }
                    }
                }
            }
            System.out.println(count);

        }
        sc.close();

    }

    public static boolean isValid(Point point1, Point point2, Point point3) {

        Line line1 = new Line(point1, point2);
        Line line2 = new Line(point1, point3);
        Line line3 = new Line(point2, point3);

        double len1 = line1.getLength();
        double len2 = line2.getLength();
        double len3 = line3.getLength();

        if (line1.isParallel(line2) || line1.isParallel(line3) || line2.isParallel(line3)) {
            return false;
        } else if ((len1 + len2) < len3 || (len1 + len3) < len2 || (len2 + len3) < len1 || Math.abs(len1 - len2) > len3
                || Math.abs(len1 - len3) > len2 || Math.abs(len2 - len3) > len1) {
            return false;
        } else {
            return true;
        }

    }

}
发表于 2018-05-21 16:33:56 回复(0)
import java.util.Scanner;

public class Main {


    public static boolean isNoTriangle(int[][] arr, int i, int j, int k) {
        if (arr[i][0] == arr[j][0]) {
            return arr[i][0] == arr[k][0];
        } else if (arr[i][0] == arr[k][0]) {
            return arr[i][0] == arr[j][0];
        } else {
            return (((double)arr[i][1] - (double)arr[j][1]) / ((double)arr[i][0] - (double)arr[j][0])) == (((double)arr[i][1] - (double)arr[k][1]) / ((double)arr[i][0] - (double)arr[k][0]));
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (!isNoTriangle(arr, i, j, k)) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}
发表于 2019-06-15 19:52:44 回复(0)
用三重循环进行穷举,只要3点不共线就能够组成三角形
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[][] points = new int[n][2];
        for(int i = 0; i < n; i++){
            String[] point = br.readLine().trim().split(" ");
            points[i][0] = Integer.parseInt(point[0]);
            points[i][1] = Integer.parseInt(point[1]);
        }
        int count = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                for(int k = j + 1; k < n; k++){
                    int x1 = points[i][0];
                    int x2 = points[j][0];
                    int x3 = points[k][0];
                    int y1 = points[i][1];
                    int y2 = points[j][1];
                    int y3 = points[k][1];
                    // 只要三个点不共线就能构成三角形
                    if((x1 - x2)*(y1 - y3) != (y1 - y2)*(x1 - x3)) count ++;
                }
            }
        }
        System.out.println(count);
    }
}

发表于 2021-04-19 15:14:37 回复(0)
python3
# 想了些骚东西,最后好像没法实现
# 最简单的做法就是,三重循环,判断所有三个点的组合是否符合三角形
# 可以通过是否共线组成三角形,这样应该还会相对快一点
# 还有另一个角度,就是看三个点钟任意两条直线是否有相同的斜率

n = int(input())
p = []
c = 0
for i in range(n):
    p.append(list(map(int, input().split())))
for i in range(n-2):   # 注意三重循环的开始于结束边界
    x1, y1 = p[i]
    for j in range(i+1, n-1):
        x2, y2 = p[j]
        for k in range(j+1, n):
            x3, y3 = p[k]
            if (y1-y2)*(x1-x3) != (y1-y3)*(x1-x2):
                c += 1
print(c)


发表于 2019-08-24 23:23:10 回复(0)
import java.awt.Point;
import java.awt.geom.Point2D;
import java.util.LinkedList;
import java.util.Scanner;
 
public classMain {
    public static void main(String[] args) {
        Scanner in = newScanner(System.in);
         
        int n = in.nextInt();
         
        LinkedList<Point2D> points = newLinkedList<>();
         
        for(inti=0; i<n; i++) {
            Point2D point = newPoint(in.nextInt(), in.nextInt());
            points.add(point);
        }
         
        int count = 0;
         
        for(Point2D point1: points) {
            for(Point2D point2: points) {
                if(point1.equals(point2)) {
                    continue;
                }
                for(Point2D point3: points) {
                    if(point3.equals(point1) || point3.equals(point2)) {
                        continue;
                    }
                    intpart1 = (int) ((point1.getX() - point3.getX()) * (point2.getY() - point3.getY()));
                    intpart2 = (int) ((point2.getX() - point3.getX()) * (point1.getY() - point3.getY()));
                    if(part1 != part2) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count / 6);
    }
}

发表于 2019-03-10 13:54:49 回复(0)
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int n =sc.nextInt();
        class point{
            int x;
            int y;
            point(int m1,int m2){
                x=m1;
                y=m2;
            }

            }

        ArrayList<point> l1 =new ArrayList<>();
        for(int i =0;i<n;i++){
            l1.add(new point(sc.nextInt(),sc.nextInt()));
        }
        int count =0;

        for(int i =0 ;i<l1.size();i++){
            for(int j =i+1;j<l1.size();j++){
                for(int k = j+1;k<l1.size();k++){
                    int a =(l1.get(i).x-l1.get(j).x)*(l1.get(i).y-l1.get(k).y);
                    int b =(l1.get(i).y - l1.get(j).y)*(l1.get(i).x-l1.get(k).x);
                    if(a != b){
                        count++;
                    }

                }
            }
        }
        
        System.out.println(count);



    }
}

发表于 2019-03-09 23:11:49 回复(1)

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct tagPoint
{
 int nX;
 int nY;
};

int main()
{
 tagPoint a[100];
 int n = 0;
 scanf("%d", &n);
 int nValue = 0;
 for (size_t i = 0; i < n; i++)
 {
  scanf("%d %d", &a[i].nX, &a[i].nY);
 }
 for (size_t i = 0; i < n; i++)
 {
  for (size_t j = i + 1; j < n; j++)
  {
   for (size_t k = j + 1; k < n; k++)
   {
    if (((a[j].nY - a[i].nY)*(a[k].nX - a[i].nX)
     - (a[k].nY - a[i].nY)*(a[j].nX - a[i].nX)) != 0)
    {
     nValue++;
    }

   }
  }
 }
 printf("%d", nValue);
 return 0;
}

发表于 2019-01-28 15:32:31 回复(0)

拼多多2018校招编程题汇总 - 题解

https://blog.csdn.net/flushhip/article/details/80366489

发表于 2018-05-19 12:30:06 回复(0)
#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> x(n,0);
    vector<int> y(n,0);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    int res=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if((x[j]-x[i])*(y[k]-y[j])!=(y[j]-y[i])*(x[k]-x[j]))
                    res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}
发表于 2019-03-11 10:59:45 回复(0)
 利用向量判断三点是否共线 (x1-x2)*(y1-y3) = (y1-y2)*(x1-x3)
 等式成立则三点共线
def helper(mlist):
    count = 0
    for i in range(len(mlist)):
        for j in range(i+1, len(mlist)):
                for k in range(j+1, len(mlist)):
                    a = (mlist[i][0] - mlist[j][0]) * (mlist[i][1] - mlist[k][1])
                    b = (mlist[i][1] - mlist[j][1]) * (mlist[i][0] - mlist[k][0])
                    if a != b:
                        count += 1
    print(count)

if __name__ == '__main__':
    n = int(input())
    mlist = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        mlist.append(tmp)
    helper(mlist)
发表于 2018-08-30 14:10:52 回复(0)
本题思路:
1.判断是否是三角形,采用三重循环的方法,最外层为点1,中间层为点2,最里层为点3,起始点均为上一层的循环控制变量。判断时满足min+mid>max && max-min<mid这个条件即可。
2.注意不能只判断长度是否满足,假如三角形的三个点共线,也是不行的。
利用向量判断三点是否共线 (x1-x2)*(y1-y3) = (y1-y2)*(x1-x3),当等式成立时,三点共线。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct point
{
    int x;
    int y;
};
bool check(point fir, point sec, point th)
{
    double len1 = sqrt((fir.x - sec.x)*(fir.x - sec.x) + (fir.y - sec.y)*(fir.y - sec.y));
    double len2 = sqrt((fir.x - th.x)*(fir.x - th.x) + (fir.y - th.y)*(fir.y - th.y));
    double len3 = sqrt((th.x - sec.x)*(th.x - sec.x) + (th.y - sec.y)*(th.y - sec.y));
    double max, mid, min;
    vector<double> data;
    data.push_back(len1);
    data.push_back(len2);
    data.push_back(len3);
    sort(data.begin(), data.end());
    min = data[0], mid = data[1], max = data[2];
    if (min + mid > max && max - min < mid)
        return true;
    else
        return false;
}
int main(void)
{
    int len;
    cin >> len;
    vector<point> data(len);
    for (int i = 0; i < len; i++)
    {
        int x, y;
        point ptemp;
        cin >> x >> y;
        ptemp.x = x;
        ptemp.y = y;
        data[i] = ptemp;
    }
    int count = 0;
    for (int i = 0; i < len-2; i++)    //点1
    {
        for (int j = i+1; j < len-1; j++)
        {
            for (int k = j + 1; k < len; k++)
            {
                if ((data[i].x - data[j].x)*(data[i].y - data[k].y) != (data[i].y - data[j].y)*(data[i].x - data[k].x))
                {
                    if (check(data[i], data[j], data[k]))
                        count++;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}


发表于 2019-04-30 15:26:01 回复(0)
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
bool in_line(double x1, double y1, double x2, double y2, double x3, double y3) {
    if (x1 == x2) { // 同一条竖线
        return x1 == x3;
    } else if(x1 == x3) {
        return x2 == x3;
    } else {
        return ((y1 - y2) / (x1 - x2)) == ((y3 - y2) / (x3 - x2));
    }
}
 
int main() {
    int n = 0;
    while (cin >> n) {
        vector<int> x(n);
        vector<int> y(n);
        for (int i = 0; i < n; ++i) {
            cin >> x[i] >> y[i];
        }
        // 迭代
        int limit1 = n - 2;
        int limit2 = n - 1;
        int cnt = 0;
        for (int i = 0; i < limit1; ++i) {
            for (int j = i + 1; j < limit2; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    cnt += !(in_line(x[i], y[i], x[j], y[j], x[k], y[k]));
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

发表于 2018-08-15 13:34:38 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, a, b;
    cin >> n;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &v[i].first, &v[i].second);
    }
    int res = 0;
    for (int i = 0; i < n; ++i) {
        map<pair<int, int>, int> mp;
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            int t = __gcd(v[i].first-v[j].first, v[i].second-v[j].second);
            ++mp[{(v[i].first-v[j].first)/t, (v[i].second-v[j].second)/t}];
        }
        for (auto &i : mp) res += i.second * (n-1-i.second);
    }
    cout << res/6 << "\n";
}

发表于 2020-12-11 09:38:25 回复(0)
def bias_slope(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
     
    if x1 == x2:
        return None, x1
    else:
        k = (y2 - y1) / (x2 - x1)
        b = (y1 * x2 - y2 * x1) / (x2 - x1)
        return k, b
     
n = int(input())
 
points = []
for i in range(n):
    t = [int(i) for i in input().split()]
    points.append(t)

pairInfo = {}
for i in range(n):
    p1 = points[i]
    for j in range(i+1, n):
        p2 = points[j]
         
        k, b = bias_slope(p1, p2)
         
        if (k, b) in pairInfo:
            pairInfo[(k, b)].extend([i, j])
        else:
            pairInfo[(k, b)] = [i, j]

for k, v in pairInfo.items():
    pairInfo[k] = set(v)

total = n * (n - 1) * (n - 2) // 6
exclude = 0

for v in pairInfo.values():
    num = len(v)
    if num > 2:
        t = num * (num - 1) * (num - 2) // 6
        exclude += t

print(total - exclude)

发表于 2020-08-01 23:21:39 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        int count = 0;
        //各顶点的x坐标数组和y坐标数组
        for(int i=0;i<n;i++){
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        if(n>=3){
            for(int i=0;i<n-2;i++){
                for(int j=i+1;j<n-1;j++){
                    for(int k=j+1;k<n;k++){
                        //利用三点共线向量公式,若不共线则可构成三角形
                        if((x[i]-x[j])*(y[i]-y[k])!=(x[i]-x[k])*(y[i]-y[j]))
                            count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}
编辑于 2020-05-05 15:13:30 回复(0)

暴力枚举直接肝
#include <stdio.h>

#define MAXN 110

int n,sum;
int x[MAXN];
int y[MAXN];

int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d%d",x+i,y+i);
	for(i=2;i<n;i++)
		for(j=0;j<i;j++)
			for(k=0;k<j;k++)
				sum += (x[i]-x[j])*(y[j]-y[k])!=(x[j]-x[k])*(y[i]-y[j]);
	printf("%d\n",sum);
	return 0;
}

发表于 2019-08-22 16:52:50 回复(0)
from math import sqrt

n = int(input())
nums = []
for _ in range(n):
    nums.append(list(map(int, input().strip().split())))


def test(xx, yy):
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                hh = (xx[i][0] - xx[j][0]) * (xx[i][1] - xx[k][1])
                kk = (xx[i][1] - xx[j][1]) * (xx[i][0] - xx[k][0])

                if hh != kk:
                    yy += 1
    return yy

print(test(nums, 0))
发表于 2019-07-27 23:54:50 回复(0)
平面上不共线的三点必能构成三角形。
发表于 2019-06-06 20:38:49 回复(0)
if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline().strip())
    # 假定最佳   C(3,n)
    total_best = n*(n-1)*(n-2)//6 #// 取整数
    locations = [] #坐标

    for line in sys.stdin: #输入
        location = list(int(x) for x in (line.split( )))
        locations.append(location)

    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                a = (locations[i][0]-locations[j][0])*(locations[i][1]-locations[k][1])
                b = (locations[i][1] - locations[j][1])*(locations[i][0]-locations[k][0])
                if a == b:
                    total_best -= 1  #有共线的三个点情况就-1
    print(total_best)

发表于 2019-05-09 15:50:35 回复(0)