首页 > 代码库 > 51nod1100(计算几何)

51nod1100(计算几何)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1100

 

题意:中文题啦~

 

思路:算斜率不用多说吧?本题唯一一个小问题是数据量是1e4,O(n^2)可能超时,我们可以用个小技巧来解决这个问题;

对这些点用x坐标排序,斜率最大的点一定是排序后相邻的两个点。

上述结论的正确性我们不难证明:

对于已排序的3个点a, b, c,通过画图我们可以知道其有3种排列方式:

1. c在ab延长线上,此时他们的斜率相等;

2. c在ab延长线下侧,很显然此时斜率最大的是ab;

3. c在ab延长线上侧,那么此时ac>ab,bc>ac,所以斜率最大的是bc;

通过上述分析我们可以发现,对于一个点x, 若其后存在点y使得斜率xy>xx+1,那么一定有y-1y>xy,所以斜率最大的两点一定是x坐标相邻的两点;

 

代码:

 1 #include <bits/stdc++.h>
 2 #define MAXN 10010
 3 using namespace std;
 4 
 5 struct Node{
 6     int x, y, number;
 7 }gg[MAXN];
 8 
 9 bool cmp(Node a, Node b){
10     return a.x<b.x;
11 }
12 
13 int main(void){
14     std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
15     int n;
16     cin >> n;
17     for(int i=0; i<n; i++){
18         cin >> gg[i].x >> gg[i].y;
19         gg[i].number=i+1;
20     }
21     sort(gg, gg+n, cmp);
22     queue<int> node1, node2;
23     double cnt=0, cc=0;
24     for(int i=1; i<n; i++){
25         cnt=(gg[i].y-gg[i-1].y)*1.0/(gg[i].x-gg[i-1].x);
26         if(cnt>cc){
27             cc=cnt;
28             while(!node1.empty()){
29                 node1.pop();
30             }
31             while(!node2.empty()){
32                 node2.pop();
33             }
34             node1.push(gg[i-1].number);
35             node2.push(gg[i].number);
36         }else if(cnt==cc){
37             node1.push(gg[i-1].number);
38             node2.push(gg[i].number);
39         }
40     }
41     while(!node1.empty()){
42         cout << node1.front() << " " << node2.front() << endl;
43         node1.pop();
44         node2.pop();
45     }
46     return 0;
47 }

 

51nod1100(计算几何)