QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235510 | #7693. Convex Hull Extension | PhantomThreshold# | WA | 0ms | 3552kb | C++20 | 2.3kb | 2023-11-02 20:49:03 | 2023-11-02 20:49:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
typedef long long db;
struct point{
db x,y;
point operator + (const point &k1){return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1){return (point){x-k1.x,y-k1.y};}
point operator * (db k1){return (point){x*k1,y*k1};}
point operator / (db k1){return (point){x/k1,y/k1};}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
point getLL(point k1,point k2,point k3,point k4){
db w1=cross(k1-k3,k4-k3);
db w2=cross(k4-k3,k2-k3);
return (k1*w2+k2*w1)/(w1+w2);
}
int n;
point a[100];
//const ll lim=4'000'000;
const ll lim=10;
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=0;i<n;i++) cin >> a[i].x >> a[i].y;
for (int i=0;i<n;i++){
point P=a[(i+n-1)%n];
point Q=a[i];
point R=a[(i+1)%n];
point S=a[(i+2)%n];
if (cross(Q-P,S-R)<=0){
cout << "infinitely many" << "\n";
return 0;
}
}
ll ans=0;
for (int i=0;i<n;i++){
point P=a[(i+n-1)%n];
point Q=a[i];
point R=a[(i+1)%n];
point S=a[(i+2)%n];
point X=getLL(P,Q,R,S);
ll mnx=Q.x-lim;
ll mxx=Q.x+lim;
mnx=min(mnx,R.x-lim);
mxx=max(mxx,R.x+lim);
mnx=min(mnx,X.x-lim);
mxx=max(mxx,X.x+lim);
// cerr << "i : " << i << endl;
for (ll x=mnx;x<=mxx;x++){
vector<ll> candy;
auto gao = [&](const point &A,const point &B,ll px){
if (A.x==B.x) return;
else{
ll w1=B.x-px;
ll w2=px-A.x;
ll fz=w1*A.y+w2*B.y;
ll fm=w1+w2;
if (fm<0) fz=-fz,fm=-fm;
if (fz%fm==0){
candy.push_back(fz/fm-1);
candy.push_back(fz/fm+1);
}
else{
if (fz>0){
candy.push_back(fz/fm);
candy.push_back(fz/fm+1);
}
else{
candy.push_back(fz/fm-1);
candy.push_back(fz/fm);
}
}
}
};
gao(P,Q,x);
gao(Q,R,x);
gao(R,S,x);
ll yl=INF;
ll yr=-INF;
for (auto y:candy){
point T={x,y};
if (cross(Q-P,T-P)<=0) continue;
if (cross(R-Q,T-Q)>=0) continue;
if (cross(S-R,T-R)<=0) continue;
yl=min(yl,y);
yr=max(yr,y);
}
ll now=max(yr-yl+1,0LL);
ans=ans+now;
}
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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: 3532kb
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: 3552kb
input:
4 -1000 1000 -1000 999 -999 999 -999 1000
output:
infinitely many
result:
wrong answer 1st lines differ - expected: '0', found: 'infinitely many'