题目链接：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;}新闻热点
疑难解答
