QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#286885 | #7862. Land Trade | PhantomThreshold | WA | 233ms | 17228kb | C++20 | 8.6kb | 2023-12-18 22:38:17 | 2023-12-18 22:38:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int __CNT=0;
typedef long double db;
const db eps=1e-12;
const db pi=acos(-1);
int sign(db k){
if (k>eps) return 1;
else if (k<-eps) return -1;
return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2] 内
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
int operator == (const point &k1) const{return cmp(x,k1.x)==0&&cmp(y,k1.y)==0;}
// 逆时针旋转
point turn(db k1){return (point){x*cos(k1)-y*sin(k1),x*sin(k1)+y*cos(k1)};}
point turn90(){return (point){-y,x};}
bool operator < (const point k1) const{
int a=cmp(y,k1.y);
if (a==-1) return 1; else if (a==1) return 0; else return cmp(x,k1.x)==-1;
}
db abs(){return sqrt(x*x+y*y);}
db abs2(){return x*x+y*y;}
db dis(point k1){return ((*this)-k1).abs();}
point unit(){db w=abs(); return (point){x/w,y/w};}
/*
void scan(){double k1,k2; scanf("%lf%lf",&k1,&k2); x=k1; y=k2;}
void print(){printf("%.11lf %.11lf\n",x,y);}
*/
friend ostream& operator << (ostream& os,const point &P){
os << "(" << P.x << "," << P.y << ")";
return os;
}
db getw(){return atan2(y,x);}
point getdel(){
if (sign(x)==-1||(sign(x)==0&&sign(y)==-1)) return (*this)*(-1);
else return (*this);
}
int getP() const{return sign(y)==-1||(sign(y)==0&&sign(x)==-1);}
};
int inmid(point k1,point k2,point k3){
return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);
}
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;}
db rad(point k1,point k2){return atan2(cross(k1,k2),dot(k1,k2));}
// -pi -> pi
int compareangle (point k1,point k2){
return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>0);
}
point proj(point k1,point k2,point q){ // q 到直线 k1,k2 的投影
point k=k2-k1; return k1+k*(dot(q-k1,k)/k.abs2());
}
int checkLL(point k1,point k2,point k3,point k4){// 求直线 (L) 线段 (S)k1,k2 和 k3,k4 的交点
return cmp(cross(k3-k1,k4-k1),cross(k3-k2,k4-k2))!=0;
}
point getLL(point k1,point k2,point k3,point k4){
db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2);
}
struct line{
// p[0]->p[1]
point p[2];
line(point k1,point k2){p[0]=k1; p[1]=k2;}
point& operator [] (int k){return p[k];}
int include(point k){return sign(cross(p[1]-p[0],k-p[0]))>0;}
point dir(){return p[1]-p[0];}
/*
line push(){ // 向外 ( 左手边 ) 平移 eps
const db eps = 1e-6;
point delta=(p[1]-p[0]).turn90().unit()*eps;
return {p[0]-delta,p[1]-delta};
}
*/
friend ostream& operator << (ostream& os,const line &L){
os << "{" << L.p[0] << "->" << L.p[1] << "}";
return os;
}
};
bool checkLL(line k1,line k2){return checkLL(k1[0],k1[1],k2[0],k2[1]);}
point getLL(line k1,line k2){return getLL(k1[0],k1[1],k2[0],k2[1]);}
int parallel(line k1,line k2){return sign(cross(k1.dir(),k2.dir()))==0;}
int sameDir(line k1,line k2){
return parallel(k1,k2)&&sign(dot(k1.dir(),k2.dir()))==1;
}
int operator < (line k1,line k2){
if (sameDir(k1,k2)) return k2.include(k1[0]);
return compareangle(k1.dir(),k2.dir());
}
int checkpos(line k1,line k2,line k3){return k3.include(getLL(k1,k2));}
int lineid=0;//0-index
vector<line> vline;
vector<tuple<db,db,db>> vabc;
int nodeid=0;//1-index
struct node{
int tp;
// 1 2 3 4 5
// & | ^ ! L
int lson;
int rson;
int line_num;
};
node vnode[200050];
int parse(const string &expr,int L,int R){
// cerr << "----------------" << endl;
// cerr << "expr : " << expr << endl;
// cerr << "L R:" << L << " " << R << endl;
// if (++__CNT==20) exit(0);
if (expr[L]=='['){
string tmp=expr.substr(L+1,R-L-1);
stringstream ss(tmp);
long long a,b,c;
ss >> a >> b >> c;
db D=-1.0*c/(a*a+b*b);
point P={D*a,D*b};
point dir={(db)b,(db)-a};
point Q=P+dir.turn90();
if (sign(a*Q.x+b*Q.y+c)<0) dir=dir*(-1.0);
vline.emplace_back(P,P+dir);
vabc.emplace_back(a,b,c);
vnode[++nodeid]={5,-1,-1,lineid};
lineid++;
return nodeid;
}
if (expr[L+1]=='!'){
int now_id=++nodeid;
vnode[now_id]={4,parse(expr,L+2,R-1),-1,-1};
return now_id;
}
int pos=-1;
int sum=0;
for (int i=L+1;i<=R-1;i++){
if (expr[i]=='(') sum++;
if (expr[i]=='[') sum++;
if (expr[i]==')') sum--;
if (expr[i]==']') sum--;
if (sum==0){
pos=i+1;
break;
}
}
// cerr << "pos,sum: " << pos << " " << sum << endl;
int now_id=++nodeid;
if (expr[pos]=='&') vnode[now_id].tp=1;
if (expr[pos]=='|') vnode[now_id].tp=2;
if (expr[pos]=='^') vnode[now_id].tp=3;
vnode[now_id].lson=parse(expr,L+1,pos-1);
vnode[now_id].rson=parse(expr,pos+1,R-1);
vnode[now_id].line_num=-1;
return now_id;
}
bool check(int x,point P){
if (vnode[x].tp==1){
return check(vnode[x].lson,P) && check(vnode[x].rson,P);
}
else if (vnode[x].tp==2){
return check(vnode[x].lson,P) || check(vnode[x].rson,P);
}
else if (vnode[x].tp==3){
return check(vnode[x].lson,P) ^ check(vnode[x].rson,P);
}
else if (vnode[x].tp==4){
return !check(vnode[x].lson,P);
}
else if (vnode[x].tp==5){
tuple<db,db,db> &abc = vabc[vnode[x].line_num];
if (sign(get<0>(abc)*P.x+get<1>(abc)*P.y+get<2>(abc))>=0) return true;
return false;
}
return false;
}
int main(){
db xl,yl,xr,yr;
cin >> xl >> xr >> yl >> yr;
string expr;
cin >> expr;
int len=expr.length();
for (auto &ch:expr) if (ch==',') ch=' ';
int Root = parse(expr,0,len-1);
point C1={(db)xl,(db)yl};
point C2={(db)xr,(db)yl};
point C3={(db)xr,(db)yr};
point C4={(db)xl,(db)yr};
vline.emplace_back(C1,C2);
vline.emplace_back(C2,C3);
vline.emplace_back(C3,C4);
vline.emplace_back(C4,C1);
lineid+=4;
/*
cerr << "stage 1" << endl;
cerr << "---------------" << endl;
cerr << "lineid : " << lineid << endl;
for (auto L:vline) cerr << L << endl;
cerr << "---------------" << endl;
cerr << "nodeid : " << nodeid << endl;
for (int i=1;i<=nodeid;i++)
cerr << "tp,l,r,lid : "
<< vnode[i].tp << " "
<< vnode[i].lson << " "
<< vnode[i].rson << " "
<< vnode[i].line_num << endl;
*/
vector<point> vp;
for (auto l1:vline){
for (auto l2:vline){
if (!checkLL(l1,l2)) continue;
point tmp=getLL(l1,l2);
if (!inmid(xl,xr,tmp.x)) continue;
if (!inmid(yl,yr,tmp.y)) continue;
vp.emplace_back(tmp);
}
}
sort(vp.begin(),vp.end());
vp.resize(
unique(vp.begin(),vp.end())-vp.begin()
);
int pnum=vp.size();
vector<vector<int>> G(pnum);
/*
cerr << "--------------" << endl;
cerr << "stage 2" << endl;
cerr << "point_num : " << pnum << endl;
for (auto p:vp) cerr << p << endl;
cerr << "--------------" << endl;
*/
for (auto l:vline){
vector<int> ps;
for (int i=0;i<pnum;i++)
if (sign(cross(l[1]-l[0],vp[i]-l[0]))==0) ps.emplace_back(i);
sort(ps.begin(),ps.end(),
[&](int idx,int idy){
return dot(l[1]-l[0],vp[idx]-l[0])<dot(l[1]-l[0],vp[idy]-l[0]);
}
);
int sz=ps.size();
for (int i=1;i<sz;i++){
G[ps[i-1]].emplace_back(ps[i]);
G[ps[i]].emplace_back(ps[i-1]);
}
}
for (int i=0;i<pnum;i++){
sort(
G[i].begin(),G[i].end(),
[&](int x,int y){
return compareangle(vp[x]-vp[i],vp[y]-vp[i]);
}
);
}
/*
for (int i=0;i<pnum;i++){
cerr << "G[" << i << "] : ";
for (auto j:G[i]) cerr << j << " ";
cerr << endl;
}
*/
db ans=0;
set<pair<int,int>> vis;
for (int i=0;i<pnum;i++){
for (auto j:G[i]){
if (vis.count(make_pair(i,j))) continue;
// cerr << "go : " << i << " " << j << endl;
vector<point> area;
int now=i;
int nxt=j;
do{
// cerr << "now,nxt : " << now << " " << nxt << endl;
area.push_back(vp[now]);
vis.emplace(make_pair(now,nxt));
int nxt_nxt=-1;
for (auto k:G[nxt]){
if (sign(cross(vp[nxt]-vp[now],vp[k]-vp[nxt]))<=0) continue;
if (vis.count(make_pair(nxt,k))) continue;
if (nxt_nxt==-1) nxt_nxt=k;
else if (sign(cross(vp[nxt_nxt]-vp[nxt],vp[k]-vp[nxt]))>0){
nxt_nxt=k;
}
}
now=nxt;
nxt=nxt_nxt;
}while (now!=i && nxt!=-1);
int cnt=area.size();
if (cnt<3) continue;
point O={(db)0.0,(db)0.0};
for (auto P:area) O=O+P;
O=O/cnt;
if (!check(Root,O)) continue;
db S=0;
for (int k=2;k<cnt;k++) S=S+cross(area[k-1]-area[0],area[k]-area[0]);
S=S/2;
ans+=S;
}
}
cout << fixed << setprecision(12) << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
0 1 0 1 ([-1,1,0]^[-1,-1,1])
output:
0.500000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
-5 10 -10 5 ((!([1,2,-3]&[10,3,-2]))^([-2,3,1]|[5,-2,7]))
output:
70.451693404635
result:
ok found '70.4516934', expected '70.4516934', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
0 1 -1 1 ([1,1,1]&[-1,-1,-1])
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
0 1000 0 1000 (([1,-1,0]&[-1000,999,999])&([1,0,-998]&[0,1,-998]))
output:
0.000500000000
result:
ok found '0.0005000', expected '0.0005000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
-725 165 643 735 ((((!(([22,15,137]|(!([23,-5,-41]^(!([2,25,-515]&[-37,10,487])))))&(!(([25,24,47]^([-24,21,-114]^[19,-7,79]))^[4,20,241]))))^(!((!((!(([30,-1,474]^([14,17,155]^[-31,-6,-153]))|[-15,-15,108]))|(([-26,-11,421]&[-15,-3,-224])&[14,-3,458])))^[9,20,-404])))^(!((!((!(([14,-6,-464]^[-11,8,...
output:
47063.334852441477
result:
ok found '47063.3348524', expected '47063.3348524', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
767 957 738 941 ((!(((!([3,-3,507]^[-30,-10,425]))^[-6,7,643])^((!((!([-11,0,450]^[21,17,-65]))&(!([17,0,64]^[-11,0,804]))))|[-31,10,-687])))&((!(([-34,12,-527]^(!([17,-14,-219]^(!([13,-27,-105]^(!([18,-47,-110]&(!([-9,-20,-455]^[-18,26,-228])))))))))^([-4,0,144]^[10,1,396])))^((!((!([35,0,-221]&[-5...
output:
36999.058655663222
result:
ok found '36999.0586557', expected '36999.0586557', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 233ms
memory: 17228kb
input:
-513 213 -733 114 (!((!((!((((!([2,16,-57]|[15,40,-272]))^((!(([0,26,315]|[5,-4,-336])^(!([-12,2,218]&([17,-16,-730]&[-7,3,-263])))))^[18,-7,29]))^[5,30,-126])^((!(((!((([8,9,406]^(!([-26,6,63]^[-38,-25,108])))^(([-9,20,220]^(!([-2,-27,213]^[29,16,-269])))|[-12,-4,-586]))^([30,0,-443]|(!((!([-17,0,3...
output:
294052.797674910655
result:
wrong answer 1st numbers differ - expected: '295728.6081036', found: '294052.7976749', error = '0.0056667'