首页 > 其他分享 >【题解】A566.三点共线

【题解】A566.三点共线

时间:2024-04-25 11:55:06浏览次数:32  
标签:arr struct int 题解 共线 斜率 三个 A566

题目大意,给定在平面直角坐标系中的多个点,判断有多少个三元组 \((A, B, C)\) 满足共线性质。

题目链接:A566.三点共线

大题思路就是暴力所有的三元组,判断三个元素的斜率是否相同即可。其实还有其他方法可以做,我个人感觉用斜率法最简单。

有几点需要注意:

  1. 在计算斜率的时候,如果多个点处于一个与横坐标轴垂直的线上,那么除以 \(0\) 的时候会爆\(\color{royalblue}\text{RE}\) 需要特判一下。

  2. 存储的时候需要使用 double 类型。

  3. 在选取三元组的时候,需要保证不重复不遗漏。不会出现一个点被多次选中,相同的组合被多次计算的情况。

  4. 斜率法

    对于三个点 \((x_1, y_1)\), \((x_2, y_2)\), 和 \((x_3, y_3)\),计算任意两点之间的斜率。如果这三个斜率相等,则这三个点共线。但是要注意的是,当两个点的 x 坐标相等时,斜率会无穷大,因此在实际计算中需要特别处理这种情况。

    \[\frac{dy}{dx} = \frac{{y_2 - y_1}}{{x_2 - x_1}} \]

#include <iostream>
using namespace std;

struct point{
    int x;
    int y;
} arr[105]; 
int n, cnt = 0;

int main(){
	cin >> n;
    for (int i=1; i<=n; i++)
        cin >> arr[i].x >> arr[i].y;
    
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            for (int k=j+1; k<=n; k++){
                int x1 = arr[i].x; int x2 = arr[j].x; int x3 = arr[k].x;
                int y1 = arr[i].y; int y2 = arr[j].y; int y3 = arr[k].y;
				if (x1 - x2 == 0 && x3 - x2 == 0){
                    cnt++;
                    continue;
                }
                if (x1 - x2 == 0 || x3 - x2 == 0) 
                    continue;
                double s1 = 1.0 * (y2 - y1) / (x2 - x1);
                double s2 = 1.0 * (y3 - y2) / (x3 - x2);
                if (s1 == s2) cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}
  1. 向量法

    设想将三个点看作向量,即 \(\vec{P_1P_2}\) 和 \(\vec{P_1P_3}\)。如果这两个向量是平行的,则三个点共线。你可以通过计算这两个向量的叉积来验证它们是否平行。如果叉积为零,则两个向量平行,即三个点共线。

    \[\text{Cross Product} = \vec{P_1P_2} \times \vec{P_1P_3} = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1) \]

#include <iostream>
using namespace std;

struct point{
    int x;
    int y;
} arr[105]; 
int n, cnt;

int main(){
	cin >> n;
    for (int i=1; i<=n; i++)
        cin >> arr[i].x >> arr[i].y;
    
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            for (int k=j+1; k<=n; k++){
                int x1 = arr[i].x; int x2 = arr[j].x; int x3 = arr[k].x; 
                int y1 = arr[i].y; int y2 = arr[j].y; int y3 = arr[k].y;
				if ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) == 0) 
					cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}
  1. 行列式法

    将三个点的坐标表示成矩阵形式,然后计算这个矩阵的行列式。如果行列式的值为零,则表示这三个点共线。有关行列式的计算可以自行在搜索引擎上搜索。

    \[\text{Determinant} = \begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix} = 0 \]

#include <iostream>
using namespace std;

struct point{
    int x;
    int y;
} arr[105]; 
int n, cnt;

int main(){
	cin >> n;
    for (int i=1; i<=n; i++)
        cin >> arr[i].x >> arr[i].y;
    
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            for (int k=j+1; k<=n; k++){
                double x1 = arr[i].x; double x2 = arr[j].x; double x3 = arr[k].x; 
                double y1 = arr[i].y; double y2 = arr[j].y; double y3 = arr[k].y;
				if (x1 * y2 + y1 * x3 + x2 * y3 - x1 * y3 - y2 * x3 - x2 * y1 == 0)
					cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}
  1. 面积法

    如果三个点 \(A(x_1, y_1)\), \(B(x_2, y_2)\), 和 \(C(x_3, y_3)\) 共线,则它们构成的三角形的面积为零。

    \[S_{area} = \frac{1}{2} |x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)| \]

#include <iostream>
using namespace std;

struct point{
    int x;
    int y;
} arr[105]; 
int n, cnt;

int main(){
	cin >> n;
    for (int i=1; i<=n; i++)
        cin >> arr[i].x >> arr[i].y;
    
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            for (int k=j+1; k<=n; k++){
                int x1 = arr[i].x; int x2 = arr[j].x; int x3 = arr[k].x; 
                int y1 = arr[i].y; int y2 = arr[j].y; int y3 = arr[k].y;
                if (0.5 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3*(y1-y2)) == 0)
					cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

以上所有代码的时间复杂度为 \(O(n^3)\),其中 \(n\) 是点的数量。但对于本题而言,没有问题不会超时。

标签:arr,struct,int,题解,共线,斜率,三个,A566
From: https://www.cnblogs.com/Macw07/p/18157305

相关文章

  • ABC350 E - Toward 0 题解
    AtCoderBeginnerContest350E-Toward0原题地址题意给定四个数NAXY,你可以对N进行以下两种操作。花费X的代价将N变成\(\lfloor\cfrac{N}{A}\rfloor\)花费Y的代价掷一颗骰子,设掷出结果是i,将N变成\(\lfloor\cfrac{N}{i}\rfloor\)你需要执行若干次......
  • 前端调用DRI后端API出现跨域资源共享(CORS)问题解决办法
    目录1.引言2.跨源资源共享和实现方法3.在Django项目中配置django-cors-headers库Reference1.引言在进行后端API开发时,有时会遇到“跨域资源共享(CORS)请求...被阻止“的错误,如图1所示。本文讲解如何在使用DRF(DjangoRESTFramework)的后端API开发项目中解决这个问题。Ac......
  • Codeforces Round 940 (Div. 2) and CodeCraft-23 题解
    CodeforcesRound940(Div.2)andCodeCraft-23题解题目链接A.Stickogon贪心#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#definedebu......
  • [HNOI2005] 星际贸易 题解
    [HNOI2005]星际贸易将问题分为两次dp。题面有:“只有一种获得最大贸易额的方法”所以直接说明了贸易额与那些费用无关。有考虑到无论干啥都要维护,第二次\(dp\)直接以暗物质为核心即可对于这里\(R\)与\(n*2\)取\(min\)的一些细节理解。我们设计状态,因为观察到了暗......
  • 洛谷 P8989 [北大集训 2021] 随机游走 题解
    前言又是随机游走?题目分析看到加边,可能性太多了。但是为了让步数最大化,我们可以贪心地想,肯定要往前面连,而且越前面要走的期望步数肯定越大。并且,我们不会浪费边在终点上。于是,题目转变成了\(1\simn-1\)连向起点\(1\)连若干条边,使得随机游走到终点的期望步数最大。那要......
  • [题解]P5431 【模板】模意义下的乘法逆元 2
    可恶,卡常好难受。P5431【模板】模意义下的乘法逆元2将分数通分,第\(i\)个分数是\(\frac{k^i*fac\diva[i]}{fac}\),\(fac\)表示所有元素的积。我们可以用\(lr,rl\)记录\(a\)的前缀后缀积,第\(i\)个分数就是\(\frac{k^i*lr[i-1]*rl[i+1]}{lr[n]}\)。这样分母都是\(lr[n]\),分子就......
  • qoj3082 Ascending Matrix 题解
    题目链接点击打开链接题目解法不考虑第\(a_{r,c}=v\)的限制怎么求?我们把条件形式化一下,发现\(k\)个区域的颜色可以表示成轮廓线的形式,即第\(i-1\)条到第\(i\)条轮廓线之间的格点颜色为\(i\)问题变成找到\(k-1\)条互不穿过的路径,起点为\((1,m)\),终点为\((n,1)\)......
  • P2882 题解
    思想一眼看上去,没什么思路。看一下标签。枚举!于是枚举\(K\)。然后变成了求最少次数。由于枚举放在第一个,我们还是考虑一下枚举。我们枚举反转区间的左端点,我们惊奇地发现,由于从左往右扫,如果左端点是朝后的,那这次不转就没机会了。所以最最简单的暴力:从左往右扫,遇到左端点......
  • 「洛谷」题解:P1217 回文质数
    题目传送门看着题目好像很简单的样子,实际上做起来才会发现,这么多函数他奶奶的是普及-难度?在这道题目当中,我们最少需要写两个函数,如果需要优化可以再多写一个,待会儿的代码我们就直接放最简单版本的了。有人说这道题可以暴力对拍之后再输出,这完全可以,但是这么简单的题目不至于使用......
  • 2022ccpc题解
    2023年第五届河南省CCPC大学生程序设计竞赛ProblemA.Mocha上小班啦思路:求n个数位的最小值,条件:每一位数字都不同切不含前导零。只需要把0放到第二位,其他按从小到大输出,大于10以后输出-1即可。#include<bits/stdc++.h>usingnamespacestd;intmain(){//预处......