QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#803646 | #9083. Two Ants | pengpeng_fudan# | AC ✓ | 1ms | 4060kb | C++23 | 8.2kb | 2024-12-07 17:53:55 | 2024-12-07 17:53:56 |
Judging History
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