QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#363372 | #2. Boat | ucup-team052 | 0 | 1ms | 4244kb | C++23 | 4.4kb | 2024-03-23 21:37:02 | 2024-03-23 21:37:03 |
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
const double eps=1e-11;
int sgn(double x)
{
if(x<-eps) return -1;
else if(x>eps) return 1;
else return 0;
}
struct Vec
{
double x,y;
Vec(double a=0,double b=0) {x=a,y=b;}
double norm() {return x*x+y*y;}
double abs() {return sqrt(x*x+y*y);}
};
Vec rdvec()
{
double x,y;
scanf("%lf %lf",&x,&y);
return Vec(x,y);
}
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (const Vec &x,const double y) {return Vec(x.x*y,x.y*y);}
Vec operator / (const Vec &x,const double y) {return Vec(x.x/y,x.y/y);}
double dis(const Vec &x,const Vec &y) {return (x-y).abs();}
double dis(const Vec &x) {return sqrt(x.x*x.x+x.y*x.y);}
void print(Vec x) {printf("%.10lf %.10lf\n",x.x,x.y);}
double cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
double cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int ccw(const Vec &x,const Vec &y,const Vec &z)
{
int w=sgn(cross(y-x,z-x));
if(w==1) return 1; // ccw
else if(w==-1) return -1; // cw;
else return 0; // coline
}
struct Seg
{
Vec s,t; // two points
Seg(Vec x,Vec y) {s=x,t=y;}
Seg() {}
Vec d() {return t-s;}
Vec point(double p) {return s+(t-s)*p;}
};
int parallel(Seg p,Seg q) {return sgn(cross(p.d(),q.d()))==0;}
Vec proj(Seg l,Vec x)
{
double p=cdot(l.t-l.s,x-l.s)/(l.t-l.s).norm();
return l.point(p);
}
int isintersect(Seg p,Seg q)
{
if(max(p.s.x,p.t.x)<min(q.s.x,q.t.x)) return 0;
if(max(q.s.x,q.t.x)<min(p.s.x,p.t.x)) return 0;
if(max(p.s.y,p.t.y)<min(q.s.y,q.t.y)) return 0;
if(max(q.s.y,q.t.y)<min(p.s.y,p.t.y)) return 0;
if(ccw(q.s,p.s,p.t)*ccw(q.t,p.s,p.t)==1) return 0;
if(ccw(p.s,q.s,q.t)*ccw(p.t,q.s,q.t)==1) return 0;
return 1;
}
Vec crosspoint(Seg p,Seg q)
{
double A=cross(p.t-p.s,q.t-q.s);
double B=cross(p.t-p.s,p.t-q.s);
return q.s+(q.t-q.s)*(B/A);
}
vector<Vec> halfPlane(vector<Seg> v) // left halfplanes
{
sort(v.begin(),v.end(),[&](Seg x,Seg y){
double ang1=atan2(x.d().y,x.d().x);
double ang2=atan2(y.d().y,y.d().x);
if(sgn(ang1-ang2)) return ang1<ang2;
else return ccw(x.s,y.s,y.t)==1;
});
auto onRight=[&](Seg s,Vec x) {return ccw(s.s,x,s.t)>=0;};
static Seg q[1005];
static Vec p[1005];
int l=0,r=0; q[0]=v[0];
for(int i=1;i<(int)v.size();i++)
{
while(l<r&&onRight(v[i],p[r])) r--;
while(l<r&&onRight(v[i],p[l+1])) l++;
q[++r]=v[i];
if(parallel(q[r],q[r-1]))
{
if(onRight(q[r],q[r-1].s)&&cdot(q[r].d(),q[r-1].d())<eps) return {};
r--;
if(!onRight(q[r],v[i].s)) q[r]=v[i];
}
if(l<r) p[r]=crosspoint(q[r],q[r-1]);
}
while(l<r&&onRight(q[l],p[r])) r--;
if(r-l<=1) return {};
p[l]=crosspoint(q[l],q[r]);
return vector<Vec>(p+l,p+r+1);
}
double Area(vector<Vec> v) // ccw
{
double ans=0;
for(int i=1;i+1<(int)v.size();i++) ans+=cross(v[i]-v[0],v[i+1]-v[0]);
return ans/2;
}
vector<Vec> convexHull(vector<Vec> a) // ccw
{
int n=a.size();
int mnx=0;
for(int i=0;i<n;i++)
{
if(a[i].x<a[mnx].x) mnx=i;
}
swap(a[mnx],a[0]);
sort(a.begin()+1,a.end(),[&](const Vec &x,const Vec &y){
return ccw(a[0],x,y)==-1||(ccw(a[0],x,y)==0&&dis(x-a[0])<dis(y-a[0]));
});
vector<int> st; int tp=0;
st.push_back(0); tp++;
for(int i=1;i<n;i++)
{
while(tp>=2&&ccw(a[st[tp-2]],a[st[tp-1]],a[i])>=0) tp--,st.pop_back();
st.push_back(i); tp++;
}
vector<Vec> ans;
for(int i=tp-1;i>=0;i--) ans.push_back(a[st[i]]);
return ans;
}
signed main()
{
int n=read();
vector<Seg> a;
Vec v0(0,0),v1(10000,0),v2(10000,10000),v3(0,10000);
a.emplace_back(v0,v1),a.emplace_back(v1,v2),a.emplace_back(v2,v3),a.emplace_back(v3,v0);
for(int i=1;i<=n;i++)
{
Vec s=rdvec(),t=rdvec();
a.emplace_back(s,t);
}
vector<Vec> ans=halfPlane(a);
if(ans.empty()) printf("0.0\n");
else printf("%.1lf\n",Area(ans));
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4244kb
input:
500 308810287 308810287 53564892 53564892 316377768 316377768 420249597 420249597 731165653 731165653 319087025 319087025 153776963 153776963 425464316 425464316 651047701 651047701 142502072 142502072 31632388 31632388 572337890 572337890 400220429 400220429 414382974 414382974 279400752 279400752 ...
output:
0.0
result:
wrong answer 1st lines differ - expected: '553232367', found: '0.0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #41:
score: 0
Wrong Answer
time: 0ms
memory: 4144kb
input:
100 191358459 947004691 342443850 366915813 22574423 36448174 228846908 747282766 190110113 253913299 93029730 879223713 290883541 747723417 162887369 973643964 586349400 863191444 242642824 878391136 18343882 502405347 18658435 174450786 308510413 787915209 79222154 665119810 422422946 793255277 53...
output:
0.0
result:
wrong answer 1st lines differ - expected: '167281196', found: '0.0'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%