1 条题解

  • 0
    @ 2021-6-15 1:39:57

    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