第一行包含一个正整数n,表示平面上有n个点(n <= 100)
第2行到第n + 1行,每行有两个整数,表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100,且保证所有坐标不同)
输出一个数,表示能构成三角形的方案数。
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; }
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;
}
}
}
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); } }
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); } }
# 想了些骚东西,最后好像没法实现 # 最简单的做法就是,三重循环,判断所有三个点的组合是否符合三角形 # 可以通过是否共线组成三角形,这样应该还会相对快一点 # 还有另一个角度,就是看三个点钟任意两条直线是否有相同的斜率 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)
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);}}
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); } }
#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;
}
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)
#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; }
#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; }
#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"; }
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)
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); } }
#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; }
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))
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)