QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#803646#9083. Two Antspengpeng_fudan#AC ✓1ms4060kbC++238.2kb2024-12-07 17:53:552024-12-07 17:53:56

Judging History

This is the latest submission verdict.

  • [2024-12-07 17:53:56]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4060kb
  • [2024-12-07 17:53:55]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;

//注意叉乘是否会爆ll
//注意凸包的最后一个点都是第一个点
//注意凸包都是逆时针的
//注意每次选凸包基准点都是x最小然后y最大
//先按x小排序再按y大排序,后面第二关键字是不能省的因为x相同时y最小/最大的点有可能会被叉积=0pop掉
template<class T>
struct vec{
    T x,y;
    vec(T _x=0,T _y=0):x(_x),y(_y){};
    int qx(){//四一二三排序,按需修改
        if(x>=0&&y>=0)  return 2;
        if(x<0&&y>=0)   return 3;
        if(x<0&&y<0)    return 4;
        if(x>=0&&y<0)   return 1;
        return -1;
    }
    void print(){cerr<<x<<' '<<y<<'\n';}
    bool operator<(vec a){
        if(qx()!=a.qx())    return qx()<a.qx();
        else{
            T p=x*a.y,q=y*a.x;
            if(p!=q)    return p>q;
            else if(a.y==0) return abs(x)>abs(a.x);
            else return abs(y)>abs(a.y);
        }
    }
    T len2(){return x*x+y*y;}
    vec operator *(T k){return {x*k,y*k};}
    vec operator +(vec a){return {x+a.x,y+a.y};}
    vec operator -(vec a){return {x-a.x,y-a.y};}
    T operator *(vec a){return x*a.x+y*a.y;}
    T operator ^(vec a){return x*a.y-y*a.x;}
    bool operator ==(vec a){return x==a.x&&y==a.y;}
    bool operator !=(vec a){return (x!=a.x||y!=a.y);}
};
template<class T>
bool check_on_line_dir(vec<T> p,vec<T> q){
    vec<__int128_t> p1={p.x,p.y};
    vec<__int128_t> q1={q.x,q.y};
    if((p1*q1)>=0&&(p1^q1)==0)  return true;
    return false;
}
template<class T>
vector<vec<T>> build_convex(vector<vec<T>> pot){//输入点集输出凸包(最后一个点和第一个点是一个点)
    sort(pot.begin(),pot.end(),[&](vec<T> a,vec<T> b){if(a.x!=b.x) return a.x<b.x;return a.y>b.y;});
    int n=pot.size();
    int lo=0;
    vector<vec<T>> res;
    for(int i=0;i<n;i++){
        while(lo>=2&&((res[lo-1]-res[lo-2])^(pot[i]-res[lo-1]))<=0)    lo--,res.pop_back();
        res.push_back(pot[i]),lo++;
    }
    int pre=lo;
    for(int i=n-2;i>=0;i--){
        while(lo>=pre+1&&((res[lo-1]-res[lo-2])^(pot[i]-res[lo-1]))<=0)    lo--,res.pop_back();
        res.push_back(pot[i]),lo++;
    }
    return res;
}
 
template<class T>
double convex_peri(vector<vec<T>> convex){//输入凸包(最后一个点和第一个点是一个点),输出凸包长度
    double len=0;
    int sz=convex.size();
    for(int i=1;i<=sz-1;i++){
        len+=sqrt((convex[i]-convex[i-1]).len2());
    }
    return len;
}
 
template<class T>
double convex_area(vector<vec<T>> convex){//输入凸包(最后一个点和第一个点是一个点),输出凸包面积
    T area=0;
    int sz=convex.size();
    for(int i=0;i<sz-2;i++){
        area+=abs((convex[0]-convex[i+1])^(convex[0]-convex[i+2]));
    }
    return (double)area/2;
}
 
 
//https://tsinghua.contest.codeforces.com/group/3T118PLOiT/contest/544779/problem/I
template<class T> 
void reorder(vector<vec<T>>& p){//将凸包变成先x最小再y最小,输入需要满足(最后一个点和第一个点是一个点)
    p.pop_back();
    rotate(p.begin(), min_element(p.begin(),p.end(), [&](vec<T> a, vec<T> b) {
		return make_pair(a.x, -a.y) < make_pair(b.x, -b.y);
	}), p.end());p.push_back(p[0]);
}
template<class T>
vector<vec<T>>  mincowsky_sum(vector<vec<T>> a,vector<vec<T>> b){//传入的是两个已经建好的且为逆时针的凸包(最后一个点和第一个点是一个点)//注意输出的凸包的相邻两个边可能是平行的
    reorder(a),reorder(b);//让a和b的第0个点是x最小然后y最大
    vector<vec<T>>  res;
    vec<T> st=a[0]+b[0];
    int s1=a.size(),s2=b.size();
    int l1=0,l2=0;
    res.push_back(st);
    while(l1!=s1-1||l2!=s2-1){
        if(l1==s1-1||(l2!=s2-1&&b[l2+1]-b[l2]<a[l1+1]-a[l1])){
            st=st+(b[l2+1]-b[l2]);l2++;
        }
        else {
            st=st+(a[l1+1]-a[l1]);l1++;
        }
        res.push_back(st);
    }
    return res;
}
 
 
 
template<class T>
struct line{
    vec<T> k,b;//k为方向,b为线上任意一个点,射线的话b为端点
    line(vec<T> dir,vec<T> pot):k(dir),b(pot) {}
};
 
template<class T>
vec<double> getnode(line<T> p,line<T> q){
    assert((p.k^q.k)!=0);
    double t=(double)((p.b-q.b)^q.k)/(q.k^p.k);
    vec<double> ans;
    ans.x=p.b.x+p.k.x*t;
    ans.y=p.b.y+p.k.y*t;
    return ans;
};
 
 
 
 
const double eps=1e-9;
template<class T>
double half_plane(vector<line<T>> line_all){//半平面交,目标面积必须在输入有向线段左边
    vector<vec<double>> convex;
    line<T> line_y(vec<T>(0,1),vec<T>(0,0)); 
    sort(line_all.begin(),line_all.end(),[&](line<T> a,line<T> b){
        if(!check_on_line_dir(a.k,b.k)) return a.k<b.k;
        else return ((b.b-a.b)^a.k)>0;
    });
    int lo=0,ro=-1;
    vector<line<T>> res;
    bool flag=false;
    auto check=[&](line<T> l,line<T> mid,line<T> r)->bool {//l,mid的交点在r左边
        if((l.k^mid.k)==0)  {flag=true;return true;}
        // cerr<<((getnode(l,mid)-vec<double>(r.b.x,r.b.y))^vec<double>(r.k.x,r.k.y))<<'\n';
        return ((getnode(l,mid)-vec<double>(r.b.x,r.b.y))^vec<double>(r.k.x,r.k.y))<eps;
    };
    int sz=line_all.size(); 
    for(int i=0;i<sz;i++){
        if(i==0)    {res.push_back(line_all[i]);ro++;continue;}
        if(check_on_line_dir(line_all[i].k,line_all[i-1].k))    continue;
        while(lo<ro&&!check(res[ro-1],res[ro],line_all[i])) {res.pop_back();ro--;}
        while(lo<ro&&!check(res[lo],res[lo+1],line_all[i])) lo++;
        res.push_back(line_all[i]);ro++;
    }
    if(flag)    return -1;
    while(lo<ro&&!check(res[ro-1],res[ro],res[lo])) ro--;
    if(ro-lo<=1)    return 0;
    if(!check(res[ro],res[lo],res[lo+1]))   return -1;
    for(int i=lo;i<=ro-1;i++)   {
        if((res[i].k^res[i+1].k)==0)  return -1;
        convex.push_back(getnode(res[i],res[i+1]));
    }
    if((res[ro].k^res[lo].k)==0)    return -1;
    convex.push_back(getnode(res[ro],res[lo]));convex.push_back(convex[0]);
    for(auto i:convex){
        if(i!=convex[0]) flag=true;
    }
    if(!flag)    return -1;
    return convex_area(convex);
}




using ld=long double;
using ll=long long;
bool on_line(vec<ll> a,vec<ll> b,vec<ll> c){//c在线段a,b上
    if(((c-a)*(c-b))<=0&&((c-a)^(c-b))==0)  return true;
    return false;
}
ll sgn(ll x){
    if(x>0) return 1;
    if(x==0) return 0;
    if(x<0) return -1;
}
bool check_1(vec<ll> a,vec<ll> b,vec<ll> c,vec<ll> d){//线段a,b和线段c,d有交点为1
    if(on_line(a,b,c)||on_line(a,b,d)||on_line(c,d,a)||on_line(c,d,b))  return true;
    return sgn((c-b)^(a-b))*sgn((d-b)^(a-b))<0&&sgn((a-d)^(c-d))*sgn((b-d)^(c-d))<0;
}
void solve(int T){
    vec<ll> a;
    vec<ll> b;
    vec<ll> c;
    vec<ll> d;
    cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
    auto print=[&](long double ans)->void {
        cout<<fixed<<setprecision(12)<<"Case "<<T<<": "<<ans<<'\n';
        return ;
    };
    if(sgn((c-a)^(b-a))==0&&sgn((d-a)^(b-a))==0){
        print(0);
        return ;
    }
    if(sgn((c-a)^(b-a))==0||sgn((d-a)^(b-a))==0){
        cout<<fixed<<setprecision(12)<<"Case "<<T<<": "<<"inf"<<'\n';
        return ;
    }
    if(sgn((c-a)^(b-a))*sgn((d-a)^(b-a))<0)    {print(0);return ;}
    vector<line<ll>> hall;
    auto rev=[&](vec<ll> k,vec<ll> b)->line<ll> {
        return line<ll>(k,b);
    };
    if(((a-b)^(c-b))>0) hall.push_back(rev(b-a,a));
    else hall.push_back(rev(a-b,b));
    
    if(((c-a)^(b-a))<0)   hall.push_back(rev(a-c,c));
    else hall.push_back(rev(c-a,a));
    if(((d-a)^(b-a))<0)   hall.push_back(rev(a-d,d));
    else hall.push_back(rev(d-a,a));

    swap(a,b);
    if(((c-a)^(b-a))<0)   hall.push_back(rev(a-c,c));
    else hall.push_back(rev(c-a,a));
    if(((d-a)^(b-a))<0)   hall.push_back(rev(a-d,d));
    else hall.push_back(rev(d-a,a));
    double res=half_plane(hall);
    // cerr<<res<<'\n';
    if(res==-1){
        cout<<fixed<<setprecision(12)<<"Case "<<T<<": "<<"inf"<<'\n';
    }
    else print(res);

      
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ =1;
    cin>>_;
    for(int T=1;T<=_;T++)   solve(T);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3784kb

input:

3
0 0 0 1 0 0 1 0
0 0 1 0 0 1 0 -1
1 1 1 2 0 0 0 3

output:

Case 1: inf
Case 2: 0.000000000000
Case 3: 0.250000000000

result:

ok 9 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 4060kb

input:

27
0 0 2 2 1 1 1 -1
0 1 0 -1 0 0 1 0
0 0 0 1 0 0 1 0
0 0 1 0 0 1 0 -1
0 0 1 0 0 0 0 1
-2 0 2 0 -1 1 1 2
-2 0 2 0 -1 1 1 1
-2 0 2 0 -1 1 3 1
-2 0 2 0 3 0 4 0
-1 1 1 1 -2 0 2 0
0 -2 2 -2 -2 0 2 0
0 -1 2 -1 -2 0 2 0
11 9 -1 20 7 -15 -6 -11
-19 -1 16 -1 11 7 -20 6
-5 -15 -19 5 9 -15 -12 15
15 9 -4 0 -17...

output:

Case 1: inf
Case 2: inf
Case 3: inf
Case 4: 0.000000000000
Case 5: inf
Case 6: inf
Case 7: inf
Case 8: inf
Case 9: 0.000000000000
Case 10: 1.000000000000
Case 11: 2.000000000000
Case 12: 1.000000000000
Case 13: inf
Case 14: inf
Case 15: 280.000000000000
Case 16: inf
Case 17: inf
Case 18: 15.88888888...

result:

ok 81 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

1000
-109 627 405 -683 431 435 -239 -644
-416 -797 -174 -217 473 -78 128 174
-150 222 -499 -601 543 -486 -523 862
-807 -905 636 -595 629 -537 -401 973
413 831 -826 -94 564 972 -855 -442
-23 580 272 -410 141 331 206 -390
-772 -874 -357 91 229 987 -590 167
-665 911 390 -273 -133 -223 910 112
-960 262 ...

output:

Case 1: 0.000000000000
Case 2: 105447.423505875340
Case 3: 0.000000000000
Case 4: inf
Case 5: 0.000000000000
Case 6: 0.000000000000
Case 7: 0.000000000000
Case 8: 0.000000000000
Case 9: 17985.252727987929
Case 10: 546679.281931133126
Case 11: inf
Case 12: inf
Case 13: 0.000000000000
Case 14: 505636....

result:

ok 3000 tokens

Extra Test:

score: 0
Extra Test Passed