QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#244335 | #7027. Machining Disc Rotors | yiyiyi | WA | 68ms | 4076kb | C++20 | 5.5kb | 2023-11-08 23:13:59 | 2023-11-08 23:14:00 |
Judging History
answer
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<bitset>
#include<set>
#define ll long long
#define lowbit(x) x&(-x)
#define mp make_pair
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define forE(i,x) for(int i=head[x];i;i=nxt[i])
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e5+5;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+(c-'0');
c=getchar();
}
return x*f;
}
using point_t=long double; //全局数据类型,可修改为 long long 等
constexpr point_t eps=1e-8;
constexpr long double PI=3.1415926535897932384l;
// 点与向量
template<typename T> struct point
{
T x,y;
bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const point &a) const {return !(*this<a || *this==a);}
point operator+(const point &a) const {return {x+a.x,y+a.y};}
point operator-(const point &a) const {return {x-a.x,y-a.y};}
point operator-() const {return {-x,-y};}
point operator*(const T k) const {return {k*x,k*y};}
point operator/(const T k) const {return {x/k,y/k};}
T operator*(const point &a) const {return x*a.x+y*a.y;} // 点积
T operator^(const point &a) const {return x*a.y-y*a.x;} // 叉积,注意优先级
int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // 向量与向量的to-left 测试 1left -1right 0on
T len2() const {return (*this)*(*this);} // 向量长度的平方
T dis2(const point &a) const {return (a-(*this)).len2();} // 两点距离的平方
// 涉及浮点数
long double len() const {return sqrtl(len2());} // 向量长度
long double dis(const point &a) const {return sqrtl(dis2(a));} // 两点距离
long double ang(const point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));} // 向量夹角
point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 逆时针旋转(给定角度)
point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 逆时针旋转(给定角度的正弦与余弦)
};
using Point=point<point_t>;
// 圆
struct Circle
{
Point c;
long double r;
bool operator==(const Circle &a) const {return c==a.c && abs(r-a.r)<=eps;}
long double circ() const {return 2*PI*r;} // 周长
long double area() const {return PI*r*r;} // 面积
// 圆与圆关系
// -1 相同 | 0 相离 | 1 外切 | 2 相交 | 3 内切 | 4 内含
int relation(const Circle &a) const
{
if (*this==a) return -1;
const long double d=c.dis(a.c);
if (d>r+a.r+eps) return 0;
if (abs(d-r-a.r)<=eps) return 1;
if (abs(d-abs(r-a.r))<=eps) return 3;
if (d<abs(r-a.r)-eps) return 4;
return 2;
}
// 圆与圆交点
vector<Point> inter(const Circle &a) const
{
const long double d=c.dis(a.c);
const int t=relation(a);
if (t==-1 || t==0 || t==4) return vector<Point>();
Point e=a.c-c; e=e/e.len()*r;
if (t==1 || t==3)
{
if (r*r+d*d-a.r*a.r>=-eps) return vector<Point>{c+e};
return vector<Point>{c-e};
}
const long double costh=(r*r+d*d-a.r*a.r)/(2*r*d),sinth=sqrt(1-costh*costh);
return vector<Point>{c+e.rot(costh,-sinth),c+e.rot(costh,sinth)};
}
};
bool cmp(pair<Point,int> u,pair<Point,int> v)
{
Point a=u.first,b=v.first;
const auto quad=[](const Point a)
{
if (a.y<-eps) return 1;
if (a.y>eps) return 4;
if (a.x<-eps) return 5;
if (a.x>eps) return 3;
return 2;
};
const int qa=quad(a),qb=quad(b);
if (qa!=qb) return qa<qb;
const auto t=a^b;
// if (abs(t)<=eps) return a*a<b*b-eps; // 不同长度的向量需要分开
return t>eps;
}
Circle O,c[maxn];
Point o={0,0};
vector<pair<Point,int>> e;
signed main()
{
int T=read();
rep(P,1,T)
{
printf("Case #%lld: ",P);
int n=read(),R=read();
e.clear();
O={{0,0},(long double)R};
rep(i,1,n) c[i]={{(point_t)read(),(point_t)read()},(point_t)read()};
rep(i,1,n)
{
auto v = O.inter(c[i]);
if((int)v.size() != 2) continue;
Point x = v[0]-c[i].c, y = v[1]-c[i].c;
if(x.toleft(y)==1) swap(v[0],v[1]);
e.push_back({v[0],0});e.push_back({v[1],1});
}
sort(e.begin(),e.end(),cmp);
long double ans=0.0;
for(auto i:e)
{
for(auto j:e)
{
Point x = i.first, y = j.first;
ans=max(ans,x.dis(y));
}
Point x = i.first;
Point rev = -x;
auto it = lower_bound(e.begin(),e.end(),make_pair(rev,0),cmp);
auto pre = it;
if(pre == e.begin()) pre=e.end(),pre--;
else pre--;
if(it == e.end()) it = e.begin();
if(it->second == 0 && pre->second == 1) ans=max(ans,O.r+O.r);
}
printf("%.15Lf\n",ans);
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
1 3 10 0 12 10 11 -6 10 -11 -6 10
output:
Case #1: 18.611654895000252
result:
ok 1 cases
Test #2:
score: -100
Wrong Answer
time: 68ms
memory: 4076kb
input:
5000 3 1000 750 500 625 -250 -625 625 -1000 1000 1000 3 8 -6 -4 5 2 5 5 8 -8 8 1 710 426 -568 994 1 10 -8 6 15 14 931 622 -651 207 -930 438 552 931 890 743 -264 -923 671 889 -315 179 15 761 173 -440 883 81 -938 -310 170 -271 981 91 918 -88 47 136 927 26 903 29 61 -162 936 22 917 129 18 32 595 431 11...
output:
Case #1: 2000.000000000000000 Case #2: 16.000000000000000 Case #3: 1420.000000000000000 Case #4: 19.843134832984429 Case #5: 1862.000000000000000 Case #6: 1190.000000000000000 Case #7: 934.000000000000000 Case #8: 542.000000000000000 Case #9: 1808.000000000000000 Case #10: 1472.000000000000000 Case ...
result:
wrong answer In case 1, expected '1998.628237512163', but found '2000.000000000000', error '0.000685881244'.