[编程题]数三角形
- 热度指数：5957 时间限制：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 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);
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)
{
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;
}
return 0;
}
发表于 2019-01-28 15:32:31
回复(0)
拼多多2018校招编程题汇总 - 题解
发表于 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)
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)
问题信息
通过挑战的用户
查看代码-
2023-03-09 13:35:05
-
2022-10-20 00:59:12 -
2022-08-27 10:47:36 -
2022-08-26 10:32:57
-
2022-08-18 15:31:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
