这两份代码有什么区别吗
  • 板块学术版
  • 楼主Lele_Programmer
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/21 22:21
  • 上次更新2024/11/22 12:16:23
查看原帖
这两份代码有什么区别吗
961972
Lele_Programmer楼主2024/11/21 22:21

调了好久,没看出什么错误。。。

AC:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 50010;
const double eps = 1e-12;
const double PI = acos(-1);

int n;
PDD q[N];
struct Circle
{
    PDD p;
    double r;
};

int sign(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int dcmp(double x, double y)
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

PDD operator+ (PDD a, PDD b)
{
    return {a.x + b.x, a.y + b.y};
}

PDD operator- (PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}

PDD operator* (PDD a, double t)
{
    return {a.x * t, a.y * t};
}

PDD operator/ (PDD a, double t)
{
    return {a.x / t, a.y / t};
}

double operator* (PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}

PDD rotate(PDD a, double b)
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}

pair<PDD, PDD> get_line(PDD a, PDD b)
{
    return {(a + b) / 2, rotate(b - a, PI / 2)};
}

Circle get_circle(PDD a, PDD b, PDD c)
{
    auto u = get_line(a, b), v = get_line(a, c);
    auto p = get_line_intersection(u.x, u.y, v.x, v.y);
    return {p, get_dist(p, a)};
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);
    double a, p;
    scanf("%lf%lf", &a, &p);
    for (int i = 0; i < n; i ++ )
    {
        q[i] = rotate(q[i], a / 180 * PI);
        q[i].x /= p;
    }

    random_shuffle(q, q + n);
    Circle c({q[0], 0});
    for (int i = 1; i < n; i ++ )
        if (dcmp(c.r, get_dist(c.p, q[i])) < 0)
        {
            c = {q[i], 0};
            for (int j = 0; j < i; j ++ )
                if (dcmp(c.r, get_dist(c.p, q[j])) < 0)
                {
                    c = {(q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2};
                    for (int k = 0; k < j; k ++ )
                        if (dcmp(c.r, get_dist(c.p, q[k])) < 0)
                            c = get_circle(q[i], q[j], q[k]);
                }
        }

    printf("%.3lf\n", c.r);

    return 0;
}

WA:

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define TIMESTAMP cerr<<fixed<<setprecision(3)<<clock()*1.0/CLOCKS_PER_SEC<<"s"<<endl;
#define _rep(i,a,b) for (int i=(a);i<=(b);++i)
#define _reps(i,a,b,c) for (int i=(a);i<=(b);c)
#define _rrep(i,a,b) for (int i=(a);i>=(b);--i)
#define _rreps(i,a,b,c) for (int i=(a);i>=(b);c)
#define _iter(i,a) for (auto i=a.begin();i!=a.end();++i)
#define _graph(i,u) for (int i=h[u];~i;i=ne[i])
#define rint register int
#define LL long long
typedef pair<int,int> pii;

const int N=50005;
const double eps=1e-12;
const double pi=acos(-1);

int n;

struct Point {
    double x,y;
    friend Point operator + (Point a,Point b) {
        return {a.x+b.x,a.y+b.y};
    }
    friend Point operator - (Point a,Point b) {
        return {a.x-b.x,a.y-b.y};
    }
    friend Point operator * (Point a,double b) {
        return {a.x*b,a.y*b};
    }
    friend Point operator / (Point a,double b) {
        return {a.x/b,a.y/b};
    }
} arr[N];

struct Line {
    Point a,b;
};

struct Circle {
    Point o;
    double r;
};

int sign(double k) {
    if (fabs(k)<eps) return 0;
    else if (k>0) return 1;
    else return -1;
}

int cmp(double a,double b) {
    if (fabs(a-b)<eps) return 0;
    else if (a>b) return 1;
    else return -1;
}

double dot(Point a,Point b) {
    return a.x*b.x+a.y*b.y;
}

double cross(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}

double area(Point a,Point b,Point c) {
    return cross(b-a,c-a);
}

Point rotate(Point a,double k) {
    return {a.x*cos(k)+a.y*sin(k),-a.x*sin(k)+a.y*cos(k)};
}

Point get_intersection(Point p,Point v,Point q,Point w) {
    auto u=p-q;
    auto t=cross(w,u)/cross(v,w);
    return p+v*t;
}

Line get_line(Point a,Point b) {
    return {(a+b)/2,rotate(b-a,pi/2)};
}

double get_dis(Point a,Point b) {
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

Circle get_circle(Point a,Point b,Point c) {
    auto p=get_line(a,b),q=get_line(a,c);
    auto o=get_intersection(p.a,p.b,q.a,q.b);
    auto r=get_dis(o,a);
    return {o,r};
}

int main() {
    scanf("%d",&n);
    _rep(i,1,n) {
        double x,y;
        scanf("%lf %lf",&x,&y);
        arr[i]={x,y};
    }
    double a,p;
    scanf("%lf %lf",&a,&p);
    _rep(i,1,n) {
        arr[i]=rotate(arr[i],a/180*pi);
        arr[i]=arr[i]/p;
    }
    random_shuffle(arr+1,arr+1+n);
    Circle c={arr[1],0};
    _rep(i,2,n) {
        if (cmp(c.r,get_dis(c.o,arr[i]))>=0) continue;
        c={arr[i],0};
        _rep(j,1,i-1) {
            if (cmp(c.r,get_dis(c.o,arr[j]))>=0) continue;
            c={(arr[i]+arr[j])/2,get_dis(arr[i],arr[j])/2};
            _rep(k,1,j-1) {
                if (cmp(c.r,get_dis(c.o,arr[k]))>=0) continue;
                c=get_circle(arr[i],arr[j],arr[k]);
            }
        }
    }
    printf("%.3lf",c.r);
    return 0;
}
2024/11/21 22:21
加载中...