QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152055 | #6118. Eartheart | Sommohito | WA | 1ms | 4004kb | C++20 | 7.2kb | 2023-08-27 16:13:58 | 2023-08-27 16:13:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef IFT
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
const long double eps=1e-3;
inline int dcmp (long double x)
{
if (fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
struct PT
{
long double x, y;
PT (long double x = 0, long double y = 0): x(x), y(y) {}
void read ()
{
scanf("%lf%lf", &x, &y);
}
void write ()
{
printf("%lf %lf", x, y);
}
bool operator == (const PT& u) const
{
return dcmp(x - u.x) == 0 && dcmp(y - u.y) == 0;
}
bool operator != (const PT& u) const
{
return !(*this == u);
}
bool operator < (const PT& u) const
{
return dcmp(x - u.x) < 0 || (dcmp(x-u.x)==0 && dcmp(y-u.y) < 0);
}
bool operator > (const PT& u) const
{
return u < *this;
}
bool operator <= (const PT& u) const
{
return *this < u || *this == u;
}
bool operator >= (const PT& u) const
{
return *this > u || *this == u;
}
PT operator + (const PT& u)
{
return PT(x + u.x, y + u.y);
}
PT operator - (const PT& u)
{
return PT(x - u.x, y - u.y);
}
PT operator * (const long double u)
{
return PT(x * u, y * u);
}
PT operator / (const long double u)
{
return PT(x / u, y / u);
}
long double operator * (const PT& u)
{
return x*u.y - y*u.x;
}
};
inline long double cross(PT a, PT b)
{
return a.x * b.y - a.y * b.x;
}
inline long double cross2(PT a, PT b, PT c)
{
return cross(b - a, c - a);
}
bool is_point_on_seg(PT a, PT b, PT p)
{
if (fabs(cross(p - b, a - b)) < eps)
{
if (p.x < min(a.x, b.x) || p.x > max(a.x, b.x)) return false;
if (p.y < min(a.y, b.y) || p.y > max(a.y, b.y)) return false;
return true;
}
return false;
}
bool seg_seg_intersection(PT a, PT b, PT c, PT d, PT &ans)
{
long double oa = cross2(c, d, a), ob = cross2(c, d, b);
long double oc = cross2(a, b, c), od = cross2(a, b, d);
if (oa * ob < 0 && oc * od < 0)
{
ans = (a * ob - b * oa) / (ob - oa);
return 1;
}
else return 0;
}
set<PT> seg_seg_intersection_inside(PT a, PT b, PT c, PT d)
{
PT ans;
if (seg_seg_intersection(a, b, c, d, ans)) return {ans};
set<PT> se;
if (is_point_on_seg(c, d, a)) se.insert(a);
if (is_point_on_seg(c, d, b)) se.insert(b);
if (is_point_on_seg(a, b, c)) se.insert(c);
if (is_point_on_seg(a, b, d)) se.insert(d);
return se;
}
#define Pt PT
#define Vector PT
struct Circle
{
Pt o;
long double r;
Circle () {}
Circle (Pt o, long double r = 0): o(o), r(r) {}
void read ()
{
o.read(), scanf("%lf", &r);
}
Pt pt(long double rad)
{
return Pt(o.x + cos(rad)*r, o.y + sin(rad)*r);
}
long double getArea (long double rad)
{
return rad * r * r / 2;
}
//area of the circular sector cut by a chord with central angle alpha
long double sector(long double alpha)
{
return r * r * 0.5 * (alpha - sin(alpha));
}
};
int getLineCircleIntersection (Pt p, Pt q, Circle O, long double& t1, long double& t2, vector<Pt>& sol)
{
// debug(p.x,p.y,q.x,q.y,O.o.x,O.o.y,O.r);
Vector v = q - p;
//sol.clear();
long double a = v.x, b = p.x - O.o.x, c = v.y, d = p.y - O.o.y;
long double e = a*a+c*c, f = 2*(a*b+c*d), g = b*b+d*d-O.r*O.r;
long double delta = f*f - 4*e*g;
if (dcmp(delta) < 0) return 0;
// if (dcmp(delta) == 0)
// {
// t1 = t2 = -f / (2 * e);
// sol.push_back(p + v * t1);
//// debug(1);
// return 1;
// }
t1 = (-f - sqrt(delta)) / (2 * e);
sol.push_back(p + v * t1);
t2 = (-f + sqrt(delta)) / (2 * e);
sol.push_back(p + v * t2);
return 2;
}
void check( vector<PT>& fig)
{
ll res = 0;
for (unsigned i = 0; i < fig.size(); i++)
{
PT p = i ? fig[i - 1] : fig.back();
PT q = fig[i];
res += (p.x - q.x) * (p.y + q.y);
}
if(res<0)
reverse(fig.begin(),fig.end());
}
int n,R;
vector<PT>v;
vector<pair<ld,int>>pq;
void maro(PT A,PT B)
{
if(abs(A.y)>abs(B.y))
swap(A,B);
ld vx=B.x-A.x,vy=B.y-A.y;
if(abs(A.y)>=R)
return;
vector<PT>sol;
long double t1,t2;
getLineCircleIntersection(PT(-1e6,0),PT(1e6,0),Circle(A,R),t1,t2,sol);
ld min_x=1e6,max_x=-1e6;
for(auto u:sol)
{
min_x=min(min_x,u.x);
max_x=max(max_x,u.x);
}
// debug(min_x,max_x,vx,vy);
ld low=0,high=1;
int cnt=1000;
while(cnt--)
{
ld mid=(low+high)/2;
PT temp=A;
temp.x+=vx*mid;
temp.y+=vy*mid;
vector<PT>sol;
long double t1,t2;
int ee=getLineCircleIntersection(PT(-1e6,0),PT(1e6,0),Circle(temp,R),t1,t2,sol);
if(ee==0)
{
high=mid;
}
else
{
low=mid;
for(auto u:sol)
{
min_x=min(min_x,u.x);
max_x=max(max_x,u.x);
// debug(u.x,u.y,temp.x,temp.y,R,cnt);
}
}
}
if(min_x<=max_x)
{
pq.push_back({min_x,2});
pq.push_back({max_x,3});
}
// cout<<"x "<<A.x<<' '<<A.y<<' '<<B.x<<' '<<B.y<<endl;
// debug(min_x,max_x);
}
void TEST_CASES()
{
cin>>n>>R;
v.resize(n);
for(int i=0; i<n; i++)
{
cin>>v[i].x>>v[i].y;
}
check(v);
// for(auto u:v)
// cout<<u.x<<' '<<u.y<<endl;
// cout<<endl;
for(int i=0; i<n; i++)
{
if(v[i].y==0&&v[(i+1)%n].y==0)
{
maro(v[i],v[(i+1)%n]);
continue;
}
auto where=seg_seg_intersection_inside(v[i],v[(i+1)%n],PT(-1e6,0),PT(1e6,0));
if(where.size()==0)
{
maro(v[i],v[(i+1)%n]);
continue;
}
auto which=*where.begin();
if(v[i].y<v[(i+1)%n].y)
{
pq.push_back({which.x,1});
debug(i,which.x,0);
}
else
{
pq.push_back({which.x,0});
debug(i,which.x,1);
}
maro(v[i],which);
maro(which,v[(i+1)%n]);
}
cout<<fixed<<setprecision(10);
sort(pq.begin(),pq.end());
debug(pq);
int hit=0;
bool on=0;
ld ans=0;
for(int i=0;i+1<pq.size();i++)
{
long double gap=pq[i+1].first-pq[i].first;
if(pq[i].second==0) on=1;
else if(pq[i].second==1) on=0;
else if(pq[i].second==2) hit++;
else hit--;
if(on&&hit==0)
ans+=gap;
}
cout<<fixed<<setprecision(9)<<ans;
}
/*
*/
int32_t main()
{
#ifndef IFT
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
4 5 -5 -5 5 -5 5 5 -5 5
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
4 5 -10 -10 10 -10 10 10 -10 10
output:
10.000000007
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 4004kb
input:
9 10 -100 -80 -90 130 -30 150 0 160 100 130 120 90 110 -60 80 -100 0 -120
output:
190.190476189
result:
wrong answer 1st numbers differ - expected: '190.15695', found: '190.19048', error = '0.00018'