Ural 2067 Friends and Berries 【思维】

本文主要是介绍Ural 2067 Friends and Berries 【思维】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.timus.ru/problem.aspx?space=1&num=2067
题意：给你2*1e5个点，定义最好的朋友是指，u和v的距离大于或等于u,v,w相互三条边的距离之和的一半，w为除了u,v任意一个点，u，v不可重复，让你输出有几对最好的朋友，并输出编号
解析：因为三点如果不共线，另外两点不可能大于三角形周长的一半，所以只能是三点共线的情况，而且u,v必须在线段的两边，所以要有只有一对最好的朋友，要么就没有

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 2*1e5+100;
int n;
struct point
{long long x,y;int id;bool operator <(const point &b)const{if(x==b.x)return y<b.y;return x<b.x;}bool operator == (const point &b)const{return x==b.x&&y==b.y;}
}a[maxn],k;
int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%I64d %I64d",&a[i].x,&a[i].y);a[i].id = i;}sort(a,a+n);k.x = a[1].x-a[0].x;k.y = a[1].y-a[0].y;int flag = 0;for(int i=2;i<n;i++){point tmp;tmp.x = a[i].x-a[i-1].x;tmp.y = a[i].y-a[i-1].y;if(tmp.x*k.y != tmp.y*k.x){flag = 1;break;}}if(flag)puts("0");else{puts("1");printf("%d %d\n",a[0].id+1,a[n-1].id+1);}return 0;
}

这篇关于Ural 2067 Friends and Berries 【思维】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---