为什么这两个程序运行所需时间差别如此之大
codeforces上的一道题，简单来说就是先输入两个点的平面坐标，以这两个点为对角的矩形上四条边的整数坐标处都有一个人，然后输入一个整数N,接下来是n行，每行是一个圆的圆心坐标及半径。要求输出不在这些圆内的人的数量。我直接暴力破解，时间是230ms,下面是代码
程序代码：#include <iostream>
#include <cmath>
using namespace std;
typedef struct
{
int x,y,r;
}rad_;
int exchange(int *a,int *b)
{
int c;
c=*b;
*b=*a;
*a=c;
return 0;
}
int main()
{
int x1,x2,y1,y2,i,j,n,sum=0;
rad_ *rads;
cin>>x1>>y1>>x2>>y2>>n;
if(x1>x2)
exchange(&x1,&x2);
if(y1>y2)
exchange(&y1,&y2);
rads=new rad_[n];
for(i=0;i<n;++i)
cin>>rads[i].x>>rads[i].y>>rads[i].r;
for(i=y1;i<=y2;++i)//检测纵向
{
for(j=0;j<n;++j)
if(rads[j].r-sqrt((x1-rads[j].x)*(x1-rads[j].x)+(i-rads[j].y)*(i-rads[j].y))>=-1e-6)
break;
if(j==n)
++sum;
for(j=0;j<n;++j)
if(rads[j].r-sqrt((x2-rads[j].x)*(x2-rads[j].x)+(i-rads[j].y)*(i-rads[j].y))>=-1e-6)
break;
if(j==n)
++sum;
}
for(i=x1+1;i<x2;++i)//检测横向
{
for(j=0;j<n;++j)
if(rads[j].r-sqrt((i-rads[j].x)*(i-rads[j].x)+(y1-rads[j].y)*(y1-rads[j].y))>=-1e-6)
break;
if(j==n)
++sum;
for(j=0;j<n;++j)
if(rads[j].r-sqrt((i-rads[j].x)*(i-rads[j].x)+(y2-rads[j].y)*(y2-rads[j].y))>=-1e-6)
break;
if(j==n)
++sum;
}
cout<<sum;
return 0;
}
看了一下别人的，最短是30ms，好几个都感觉跟我的差不多，下面贴一个程序代码：#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <ctime>
#include <cmath>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define FE(v,itr) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
#define SZ(x) ((int) (x).size())
#define RA(x) (x).begin(), (x).end()
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define PB push_back
#define MP make_pair
#define INF 2000000000
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
int x1,x2,y3,y2,n;
int x[1005],y[1005],r[1005];
int main() {
int w,ww,www,wwww;
cin>>w>>ww>>www>>wwww;
x1 = min(w,www); x2 = max(w,www); y3 =min(ww,wwww); y2 = max(ww,wwww);
cin>>n; int i,j,k;
REP(i,n) {
cin>>x[i]>>y[i]>>r[i];
}
int ans=0;
for(i=x1;i<=x2;i++) {
int warm = 0;
REP(j,n) {
if ((x[j]-i)*(x[j]-i) + (y[j]-y3)*(y[j]-y3) <= r[j]*r[j]) {
warm = 1; break;
}
}
if (!warm) ans++;
}
for(i=x1;i<=x2;i++) {
int warm = 0;
REP(j,n) {
if ((x[j]-i)*(x[j]-i) + (y[j]-y2)*(y[j]-y2) <= r[j]*r[j]) {
warm = 1; break;
}
}
if (!warm) ans++;
}
for(i=y3+1;i<y2;i++) {
int warm = 0;
REP(j,n) {
if ((x[j]-x1)*(x[j]-x1) + (y[j]-i)*(y[j]-i) <= r[j]*r[j]) {
warm = 1; break;
}
}
if (!warm) ans++;
}
for(i=y3+1;i<y2;i++) {
int warm = 0;
REP(j,n) {
if ((x[j]-x2)*(x[j]-x2) + (y[j]-i)*(y[j]-i) <= r[j]*r[j]) {
warm = 1; break;
}
}
if (!warm) ans++;
}
cout << ans << endl;
cin.get();
cin.get();
return 0;
}但是时间就差了这么多。以前也遇到过，明明差不多，我要30ms，别人10ms，试着复制别人的提交上去还是30ms！崩溃……
