1 条题解
-
0
C++ :
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int N = 100007; int X1, Y1, X2, Y2; struct Target {int d1, d2;} t1[N], t2[N]; inline int Dist(int a, int b) {return a * a + b * b;} bool cmp1(const Target& a, const Target& b) {return a.d1 < b.d1;} bool cmp2(const Target& a, const Target& b) {return a.d2 < b.d2;} int main() { int n, i, j, x, y, Res = 0x7fffffff; cin >> X1 >> Y1 >> X2 >> Y2 >> n; for (i = 0; i < n; ++i) { scanf("%d%d", &x, &y); t1[i].d1 = t2[i].d1 = Dist(x - X1, y - Y1); t1[i].d2 = t2[i].d2 = Dist(x - X2, y - Y2); } sort(t1, t1 + n, cmp1); sort(t2, t2 + n, cmp2); j = n - 1; for (i = 0; i < n; ++i) { while (t2[j].d1 <= t1[i].d1 && j >= 0) --j; if (j == -1) Res = min(Res, t1[i].d1); else Res = min(Res, t1[i].d1 + t2[j].d2); } cout << Res << endl; return 0; }
Pascal :
var x,y,x1,y1,x2,y2,i,n,min,j:longint; a,b:array[1..100500]of longint; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; begin read(x,y,x1,y1); read(n); for i:=1 to n do begin read(x2,y2); a[i]:=sqr((x2-x))+sqr((y2-y)); b[i]:=sqr((x2-x1))+sqr((y2-y1)); end; sort(1,n); min:=a[n];i:=n;j:=b[n]; while i>=1 do begin if b[i]>j then j:=b[i]; dec(i); while (b[i]<=j) and (i>0) do dec(i); if a[i]+j<min then min:=a[i]+j; end; writeln(min); end.
- 1
信息
- ID
- 278
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者