題目鏈接：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;}新聞熱點
疑難解答
