QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244229#7693. Convex Hull ExtensionSolitaryDream#WA 0ms3608kbC++173.0kb2023-11-08 22:04:042023-11-08 22:04:04

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 22:04:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3608kb
  • [2023-11-08 22:04:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef double db;
typedef long long ll;
const int N=55;
struct Point {
    int x,y;
    Point operator +(const Point &s) const{
        return {x+s.x,y+s.y};
    }
    Point operator -(const Point &s) const{
        return {x-s.x,y-s.y};
    }
    int Len2() const{
        return x*x+y*y;
    }
};
int det(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}
db intersetion(Point a,Point b,Point c,Point d) {
    return a.x+(b-a).x*(1.0*det(d-c,a-c)/det(b-a,d-c));
}
ll f(ll n,ll a,ll b,ll m) {
    if(b==0) return n*(a/m);
    if(a>=m) return n*(a/m)+f(n,a%m,b,m);
    if(b>=m) return (n-1)*n/2*(b/m)+f(n,a,b%m,m);
    return f((a+b*n)/m,(a+b*n)%m,m,b);
}
ll g(ll n,ll a,ll b,ll m) {
    if(m<0) m=-m,a=-a,b=-b;
    if(b<0) {
        a+=b*(n-1);
        b=-b;
    }
    ll s=0;
    if(a<0) {
        ll aa=(a%m+m)%m;
        s-=(aa-a)/m*n;
        a=aa;
    }
    return s+f(n,a,b,m);
}
const db eps=1e-9;
db mnx;
ll solve(Point a,Point b,db l,db r) {
    if(a.x==b.x) return 0;
    if(l>r) swap(l,r);
    if(fabs(mnx-l)<1e-6) l+=eps;
    ll xl=ceil(l),xr=floor(r-eps);
    if(a.x>b.x) {
        return g(xr-xl+1,-(-a.x*b.y+b.x*a.y+xl*(b.y-a.y))-1,-(b.y-a.y),-(b.x-a.x));
    } else {
        // if(l==-5 && r==-1) cerr << xl << ' ' << xr << endl;
        return -g(xr-xl+1,-a.x*b.y+b.x*a.y+xl*(b.y-a.y),b.y-a.y,b.x-a.x);
    }
}
Point a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    FOR(i,0,n-1) cin >> a[i].x >> a[i].y;
    ll res=0;
    FOR(i,0,n-1) {
        int j=(i+1)%n,k=(j+1)%n,h=(k+1)%n;
        int s=det(a[j]-a[i],a[h]-a[k]);
        if(s<0) {
            cout << "infinitely many\n";
            return 0;
        }
        if(s==0) {
            if((a[j]-a[k]).Len2()==1) {
                if(abs(a[j].x-a[k].x)==1) {
                    if((a[i].x-a[j].x)%abs(a[i].y-a[j].y)==0) {
                        cout << "infinitely many\n";
                        return 0;
                    }
                }
                if(abs(a[j].y-a[k].y)==1) {
                    if((a[i].y-a[j].y)%abs(a[i].x-a[j].x)==0) {
                        cout << "infinitely many\n";
                        return 0;
                    }
                }
            } else {
                cout << "infinitely many\n";
                return 0;
            }
        }
        db px=intersetion(a[i],a[j],a[k],a[h]);
        mnx=min({px,(db)a[j].x,(db)a[k].x});
        res+=solve(a[i],a[j],a[j].x,px);
        res+=solve(a[k],a[h],a[k].x,px);
        res+=solve(a[k],a[j],a[j].x,a[k].x);
        // if(i==0) {
        //     cerr << solve(a[i],a[j],a[j].x,px) << ' ' << solve(a[k],a[h],a[k].x,px) << ' ' << solve(a[k],a[j],a[j].x,a[k].x) << endl;
        // }
        // cerr << a[j].x << ' ' << a[j].y << ' ' << res << endl;
    }
    cout << res << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

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

output:

23

result:

ok single line: '23'

Test #2:

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

input:

4
-7 -7
7 -7
7 7
-7 7

output:

infinitely many

result:

ok single line: 'infinitely many'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

4
-1000 1000
-1000 999
-999 999
-999 1000

output:

infinitely many

result:

wrong answer 1st lines differ - expected: '0', found: 'infinitely many'