直线()-其他

发表于： 3月 19, 2023 3月 19, 2023
分类：其他
标签：其他

直线()

直线

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上 2 × 3 个整点
(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z，即横坐标是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。

给定平面上 20 × 21 个整点
(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z，即横坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。

请问这些点一共确定了多少条不同的直线。

运行限制

最大运行时间：1s
最大运行内存: 128M

分析

两点式：已知直线l上的两点P1(x1，y1)、P2(x2，y2)，(x1≠x2)

直线方程是(y-y1)/(y2-y1)=(x-x1)/(x2-x1)

由上式可得

y=(y2-y1)/(x2-x1)x-(x2y1-y2x1)/(x2-x1)

则k=(y2-y1)/(x2-x1)
b=(x2y1-y2x1)/(x2-x1)

提交答案

#include<bits/stdc++.h>
using namespace std;
struct Point{//定义结构体 
    double x, y;
}p[25*25];
map<pair<double,double>,int> line;//pair 存斜率k和截距b，表示直线line 用map去重 
int main(){
    int cnt = 0;
    int col = 20, row = 21;//横坐标是0到19(包含0和19)之间的整数，那么竖线有20条，即col=20；纵坐标是0到20，那么有21条横线，即row=21
    for(int i=0; i<col; i++)//枚举所有点，存入数组p中 
        for(int j=0; j<row; j++){
            p[cnt].x = i;
            p[cnt++].y = j;
        } 
    int linenum = row + col;//横线和竖线条数加起来先计入linenum，初值linenum=row+col 
    for(int i=0; i<cnt; i++)
        for(int j=0; j<cnt; j++){//枚举所有点 
            if(p[i].x == p[j].x || p[i].y == p[j].y) continue;//如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条
            double k = (p[j].y - p[i].y) / (p[j].x - p[i].x);//计算直线的斜率k 
            double b = ((p[j].x * p[i].y) - (p[j].y * p[i].x)) / (p[j].x - p[i].x);//计算直线的截距b 
            //判断(i,j)构造出来的直线line(k,b)是否之前已经计入过linenum中 
            if(line[{k,b}] == 0){//如果是初次遇见的新直线line，那么就map其为1，并且计入linenum，即linenum++；
//否则表示之前已经出现过此直线line(k,b)，就无需统计 
                line[{k,b}] = 1;
                linenum ++;
            }
        }
    cout << linenum << endl;
    return 0;
}

————————

直线