140 条题解
-
2hanye LV 6 @ 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;
} -
22018-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);
}
} -
02023-07-18 10:26:35@
#include<bits/stdc++.h> 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); } }
-
02020-05-23 15:30:08@
dgbcccmmmmmmm
-
02009-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])) -
02009-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 有效耗时:9msqsort+枚举就有如此效率
-
02009-07-11 23:22:21@
额。当我没说。又看错题。。。
King465656你改成int64看看 -
02009-07-08 19:05:20@
分治典型题。
一开始写了个快排,没有加到程序里,WA了两次还死命的查错,太囧了。 -
02009-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)
就全错。。。
这个是。。。什么问题 -
02009-05-12 22:08:26@
分治法
procedure find(li,ri:longint);
var
i,j,m:longint;
d:double;
begin
if ri -
02009-05-05 11:08:19@
总的来说,数据弱的可以,puppy快的可以。
貌似都是随机数据。离散化+下界判定(if (a[j,1]-a>min) then break;)
pascal,错误207的话,把保存点的数组定义为int64,因为2^32*2^32>maxlongint
-
02009-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 -
02009-03-18 15:56:21@
快排,确定最优解范围+枚举
p:=1;
for i:=1 to n do
begin
p:=i+1;
while (x[p]-x[i] -
02009-03-13 19:41:17@
想起了RYH大牛以前山寨的《魔兽争霸》了~~~~~~~~~
-
02009-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 -
02009-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的就直接搜索剪枝。。。就是上面的。。。
正解貌似是分治。。不过编程复杂度大。。时间划不来。。 -
02009-01-24 14:01:39@
其实....加一个最简单的剪枝就能过- -
时间很恐怖:
Accepted 有效得分:100 有效耗时:25859msfor(int i=1;i
-
02009-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 -
02008-12-19 22:37:35@
break 打成了 continue …………… TEL了两次~!
细心那~!Accepted 有效得分:100 有效耗时:212ms
-
02008-12-07 10:34:20@
puppy 0ms