139 条题解

  • 1
    @ 2021-05-06 17:10:01

    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<iomanip>
    #include<memory.h>
    #include<time.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<stdbool.h>
    #include<math.h>
    #define min(a,b) ((a)<(b)?(a):(b))
    #define max(a,b) ((a)>(b)?(a):(b))
    #define abs(a) ((a)>0?(a):(-(a)))
    #define lowbit(a) (a&(-a))
    #define sqr(a) ((a)*(a))
    #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
    #define eps 1e-8
    #define J 10000
    #define MAX 0x7f7f7f7f
    #define PI 3.1415926535897
    #define N 100004
    using namespace std;
    int n,m,lll,ans,cas;
    double b,c;
    struct xxx
    {
    double x,y;
    }a[N];
    bool cmp(xxx aa,xxx bb)
    {
    if(aa.x!=bb.x)return aa.x<bb.x;
    return aa.y<bb.y;
    }
    int main() {
    int i,j,k;
    while(~scanf("%d",&n) && n)
    {
    c=1000000000000;
    for(i=1;i<=n;i++)
    scanf("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,cmp);
    for(i=1;i<=n;i++)
    {
    for(j=i+1;j<=n;j++)
    {
    if(sqr(a[i].x-a[j].x)>c)break;
    b=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
    c=min(c,b);
    }
    }
    c=sqrt(c);
    printf("%.3lf\n",c);
    }
    return 0;
    }

  • 1
    @ 2018-11-29 22:50:54

    简单的枚举和快排而已。

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define sqr(x) x*x
    using namespace std;

    int n;
    double ans;
    struct lx
    {
    double x,y;
    }p[100005];

    bool cmp(lx a,lx b)
    {
    return (sqr(a.x)+sqr(a.y))<(sqr(b.x)+sqr(b.y));
    }

    int main()
    {
    while(~scanf("%d",&n))
    {
    for (int i=1;i<=n;i++)
    scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp);
    ans=sqrt(sqr((p[n].x-p[1].x))+sqr((p[n].y-p[1].y)));
    for (int i=1;i<=n;i++)
    {
    int k=i+1;
    while (p[k].y-p[i].y<ans&&k<n) k++;
    for (int j=i+1;j<=k;j++)
    {
    ans=min(ans,sqrt(sqr((p[j].x-p[i].x))+sqr((p[j].y-p[i].y))));
    }
    }
    printf("%.3lf\n",ans);
    }
    }

  • 0
    @ 2020-05-23 15:30:08

    dgbcccmmmmmmm

  • 0
    @ 2009-07-18 14:36:47

    水题

    准确说数据太弱

    看红色部分,这是看RP的:

    begin

    Min:=999999999999999999;

    Read(n);

    For i:=1 to n do

    read(x[i],y[i]);

    qsort(1,n);

    For i:=1 to n-1 do

    For j:=i+1 to Mm(i+10,n) do

    IF sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))

  • 0
    @ 2009-07-14 22:22:32

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 9ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:9ms

    qsort+枚举就有如此效率

  • 0
    @ 2009-07-11 23:22:21

    额。当我没说。又看错题。。。

    King465656你改成int64看看

  • 0
    @ 2009-07-08 19:05:20

    分治典型题。

    一开始写了个快排,没有加到程序里,WA了两次还死命的查错,太囧了。

  • 0
    @ 2009-07-08 16:25:57

    有一个很囧很强大的问题

    快排如果这样打

    While XMid do Dec(J);

    (Mid:=X[(I+J) Div 2];Mid:Extended)

    就对了

    但是如果是

    While XX[Mid] do Dec(J);

    (Mid:=(I+J)Div 2;Mid:Longint)

    就全错。。。

    这个是。。。什么问题

  • 0
    @ 2009-05-24 13:10:44

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    快排+枚举(剪枝)

    var x,y:array[0..100010]of double;

    n:longint;

    procedure init;

    var i:longint;

    begin

    readln(n);

    for i:=1 to n do

    readln(x[i],y[i]);

    end;

    procedure kp(st,ed:longint);

    var i,j:longint;

    q,t:double;

    begin

    i:=st;

    j:=ed;

    q:=x[(i+j)div 2];

    repeat

    while x[i]q do dec(j);

    if ij;

    if st

  • 0
    @ 2009-05-12 22:08:26

    分治法

    procedure find(li,ri:longint);

    var

    i,j,m:longint;

    d:double;

    begin

    if ri

  • 0
    @ 2009-05-05 11:08:19

    总的来说,数据弱的可以,puppy快的可以。

    貌似都是随机数据。

    离散化+下界判定(if (a[j,1]-a>min) then break;)

    pascal,错误207的话,把保存点的数组定义为int64,因为2^32*2^32>maxlongint

  • 0
    @ 2009-03-25 21:56:31

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 56ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 9ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 56ms

    ├ 测试数据 08:答案正确... 88ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 88ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:297ms

  • 0
    @ 2009-03-18 15:56:21

    快排,确定最优解范围+枚举

    p:=1;

    for i:=1 to n do

    begin

    p:=i+1;

    while (x[p]-x[i]

  • 0
    @ 2009-03-13 19:41:17
    想起了RYH大牛以前山寨的《魔兽争霸》了~~~~~~~~~
    
  • 0
    @ 2009-02-23 21:37:20

    PROGRAM JamesBend;

    var

    s:array[1..100000] of record

    x:int64;

    y:int64;

    end;

    w,min:real;

    i,j,n:longint;

    procedure change(a,b:int64);

    var

    c:int64;

    begin

    c:=s[a].x;

    s[a].x:=s.x;

    s.x:=c;

    c:=s[a].y;

    s[a].y:=s.y;

    s.y:=c;

    end;

    function dis(a,b:int64):real;

    begin

    dis:=sqrt(sqr(s[a].x-s.x)+sqr(s.y-s[a].y));

    end;

    procedure quiksort(h,t:int64);

    var

    pivot,i,j:int64;

    begin

    if hs[i].x do inc(i);

    while pivoth then quiksort(1,j);

    if i)=min then break

    else

    begin

    w:=dis(i,j);

    if w

  • 0
    @ 2009-01-31 12:13:48

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    这道题目只是想AC的就直接搜索剪枝。。。就是上面的。。。

    正解貌似是分治。。不过编程复杂度大。。时间划不来。。

  • 0
    @ 2009-01-24 14:01:39

    其实....加一个最简单的剪枝就能过- -

    时间很恐怖:

    Accepted 有效得分:100 有效耗时:25859ms

    for(int i=1;i

  • 0
    @ 2009-01-05 22:33:13

    时间很丑。。。具体思想,先排序,然后分治。

    详细的见这里:http://cai0715.wvpmx.com/?p=45

    编译通过...

    ├ 测试数据 01:答案正确... 353ms

    ├ 测试数据 02:答案正确... 541ms

    ├ 测试数据 03:答案正确... 259ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 400ms

    ├ 测试数据 06:答案正确... 181ms

    ├ 测试数据 07:答案正确... 447ms

    ├ 测试数据 08:答案正确... 603ms

    ├ 测试数据 09:答案正确... 150ms

    ├ 测试数据 10:答案正确... 525ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:3459ms

  • 0
    @ 2008-12-19 22:37:35

    break 打成了 continue …………… TEL了两次~!

    细心那~!

    Accepted 有效得分:100 有效耗时:212ms

  • 0
    @ 2008-12-07 10:34:20

    puppy 0ms

信息

ID
1012
难度
7
分类
计算几何 点击显示
标签
递交数
3926
已通过
839
通过率
21%
被复制
8
上传者