寻找切线

2024-06-16 19:32

文章标签 寻找切线

本文主要是介绍寻找切线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1687 : 寻找切线

描述

给定平面上N个点P1=(X1, Y1), P2=(X2, Y2), … PN=(XN, YN)。
请你从中找到两个不同的点Pi和Pj满足：其他所有点都在Pi和Pj连线的同一侧(可以在连线上)。
如果有多组答案满足条件，你可以输出任意一组。

line

输入
第一行包含一个整数N。

以下N行每行包含两个整数Xi和Yi。

对于50%的数据，1 ≤ N ≤ 1000

对于100%的数据，1 ≤ N ≤ 100000,0 ≤ Xi, Yi ≤ 1000000

输出
输出由一个空格隔开的两个整数i和j，注意1 ≤ i, j ≤ N且i ≠ j。

样例输入

样例输出

5 6

坑点
题目输出的是第几个点，需要从1开始，我第一次写的时候是从0开始的，导致死活过不去

思路
这道题的思路有点想计算几何里面的凸包
找一个点，这个点的横坐标最小，当然也可以是其他的，按照样例里面的就是（0，10）了，然后遍历所有的点，找到的另一个点与这个点的斜率最大，就是所求的点了，要注意斜率为正无穷的情况，所以要判断横坐标的差值是否为0

直接放这道题的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
struct node
{int x,y;
};
struct node a[100005];//把每个点都存起来
int main()
{int n;while(cin>>n){struct node t;int tnum;t.x = 9999;for(int i = 0; i < n; i++){scanf("%d%d",&a[i].x,&a[i].y);if(a[i].x < t.x)//找到最左边的一个点，这个点肯定在凸包的边上，这里不做证明{t = a[i];tnum = i;}}double ans = -100;int tans = 0;for(int i = 0; i < n; i++){if(tnum != i){if((a[i].x - t.x) == 0)//如果共线的话，直接选择这个点就好，不要寻找斜率，会出错的{tans = i;break;}else{double tt = (a[i].y - t.y)/(double)(a[i].x - t.x);//找到斜率最大的另一个点if(tt > ans){ans = tt;tans = i;}}}}cout << tnum+1 <<" "<< tans+1 << endl;}return 0;
}