QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202395#5155. Faster Than LightPhantomThresholdWA 0ms53988kbC++147.3kb2023-10-06 00:23:372023-10-06 00:23:37

Judging History

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

  • [2023-10-06 00:23:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:53988kb
  • [2023-10-06 00:23:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

//#define DEBUG

typedef __int128 ll;
struct frac{
	ll p,q;
	inline frac(){p=0;q=1;}
	inline frac(ll x){p=x,q=1;}
	inline frac(ll x,ll y){ll d=__gcd(x,y);p=x/d,q=y/d;if(q<0) p=-p,q=-q;}
	inline frac operator + (const frac &x) const{return frac(p*x.q+q*x.p,q*x.q);}
	inline frac operator - (const frac &x) const{return frac(p*x.q-q*x.p,q*x.q);}
	inline frac operator - () const{return frac(-p,q);}
	inline frac operator * (const frac &x) const{return frac(p*x.p,q*x.q);}
	inline frac operator / (const frac &x) const{return frac(p*x.q,q*x.p);}
	
	inline bool operator < (const frac &x) const{return p*x.q<q*x.p;}
	inline bool operator <= (const frac &x) const{return p*x.q<=q*x.p;}
	inline bool operator == (const frac &x) const{return p*x.q==q*x.p;}
	inline bool operator > (const frac &x) const{return p*x.q>q*x.p;}
	inline bool operator >= (const frac &x) const{return p*x.q>=q*x.p;}
	
	inline bool operator != (const frac &x) const{return p*x.q!=q*x.p;}
	void print(){
		cerr << (long long)p << "/" << (long long) q;	
	}
};

#ifdef DEBUG
typedef long double db;
#else
typedef frac db;
#endif

const db INF=1e9;

#ifdef DEBUG
const db eps=0;
#else
const db eps=0;
#endif

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;}
struct point{
	db x,y;
	point operator + (const point &k1) const{return (point){x+k1.x,y+k1.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 turn90(){
		return (point){-y,x};
	}
	db abs2(){
		return x*x+y*y;	
	}
	int getP() const{
		return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);	
	}
	#ifdef DEBUG
	void print(){
		cerr << "(" << x << "," << y << ") ";	
	}
	#else
	void print(){
		cerr << "(";
		x.print();
		cerr << ",";
		y.print();
		cerr << ") ";	
	}
	#endif
};

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;	
}
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){
	point k=k2-k1;
	return k1+k*(dot(q-k1,k)/k.abs2());
}
int checkLL(point k1,point k2,point k3,point 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);
	db w2=cross(k4-k3,k2-k3);
	return (k1*w2+k2*w1)/(w1+w2);	
}

struct line{
	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];}
	#ifdef DEBUG
	void print(){
		p[0].print();
		cerr << "-> ";
		p[1].print();
		cerr << " ";
	}
	#else
	void print(){
		p[0].print();
		cerr << "-> ";
		p[1].print();
		cerr << " ";
	}
	#endif
};
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));
//	assert(sign(cross(k1.dir(),k2.dir()))!=0);
//	assert(sign(cross(k1.dir(),k3.dir()))!=0);
	if (sign(cross(k1.dir(),k2.dir()))<0) swap(k1,k2);
	bool flag=sign(cross(k1.dir(),k3.dir()))>0;
	
	db rate1=0,rate2=0;
	{
		if (sign(cross(k1.dir(),k2.dir()))==0){
			return sign(cross(k1[0]-k2[0],k2[1]-k2[0]))>=0;
		}
		db w1=cross(k1[0]-k2[0],k2[1]-k2[0]);
		db w2=cross(k2[1]-k2[0],k1[1]-k2[0]);
		rate1=w1/(w1+w2);
	}
	{
		
		if (sign(cross(k1.dir(),k3.dir()))==0){
			return sign(cross(k1[0]-k3[0],k3[1]-k3[0]))>=0;
		}
		
		db w1=cross(k1[0]-k3[0],k3[1]-k3[0]);
		db w2=cross(k3[1]-k3[0],k1[1]-k3[0]);
		rate2=w1/(w1+w2);
	}
	if (flag) return rate1<=rate2;
	else return rate1>=rate2;
}
vector<line> getHL(vector<line> &L){
	sort(L.begin(),L.end());
	
	deque<line> q;
	for (int i=0;i<(int)L.size();i++){
		if (i && sameDir(L[i],L[i-1])) continue;
		while (q.size()>1 && !checkpos(q[q.size()-2],q[q.size()-1],L[i])) q.pop_back();
		while (q.size()>1 && !checkpos(q[1],q[0],L[i])) q.pop_front();
		q.push_back(L[i]);
	}
	while (q.size()>2 && !checkpos(q[q.size()-2],q[q.size()-1],q[0])) q.pop_back();
	while (q.size()>2 && !checkpos(q[1],q[0],q[q.size()-1])) q.pop_front();
	vector<line> ans;
	for (int i=0;i<(int)q.size();i++) ans.push_back(q[i]);
	return ans;
}

const int maxn=400000;
int n;
point a[maxn+50];
point b[maxn+50];

void gao1(vector<line> &L,db x,db y){
	point P=(point){0,y};
	point Q=(point){1,y-x};
	point R=P+(Q-P).turn90();
	if (R.x*x+R.y>y) swap(P,Q);
	L.emplace_back(P,Q); 
}
void gao2(vector<line> &L,db x,db y){
	point P=(point){0,y};
	point Q=(point){1,y-x};
	point R=P+(Q-P).turn90();
	if (R.x*x+R.y<y) swap(P,Q);
	L.emplace_back(P,Q); 
}

bool checkXY(vector<pair<int,int>> &v){
	int sz=v.size();
	sort(v.begin(),v.end(),
		[&](const pair<int,int> &A,const pair<int,int> &B){
			return A.second<B.second;	
		}
	);
	int mxl=-1e9;
	for (int i=0;i<sz;i++) mxl=max(mxl,v[i].first);
	if (mxl<=v[0].second) return true;
	return false;
}

bool checkOK(vector<line> &L){
	if (L.size()<=2) return false;
	int sz=L.size();
	
	int pos=0,npos=1;
	for (int i=0;i<sz;i++){
		int nxt=(i+1)%sz;
		if (!sameDir(L[i],L[nxt])){
			pos=i;
			npos=nxt;
		}
	}
	for (int i=0;i<sz;i++){
		if (i==pos || i==npos) continue;
		if (!checkpos(L[pos],L[npos],L[i])) return false;
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	vector<pair<int,int>> vx;
	vector<pair<int,int>> vy; 
	cin >> n;
	for (int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		a[i]=(point){db(x1),db(y1)};
		b[i]=(point){db(x2),db(y2)};
		vx.emplace_back(x1,x2);
		vy.emplace_back(y1,y2);
	}
	if (checkXY(vx) || checkXY(vy)){
		cout << "possible" << "\n";
		return 0;	
	}
	
	{
		vector<line> L;
		L.emplace_back((point){db(0),db(1)},(point){db(0),db(0)});
		L.emplace_back((point){db(INF),db(0)},(point){db(INF),db(1)});
		
		for (int i=1;i<=n;i++){
			gao1(L,a[i].x,b[i].y);
			gao2(L,b[i].x,a[i].y);
		}
		gao1(L,0,INF);
		gao2(L,INF,0);
		#ifdef DEBUG
		cerr << "----------------" << endl;
		for (auto l:L){
			l.print();
			cerr << endl;	
		}
		#endif
		L=getHL(L);
		#ifdef DEBUG
		cerr << "----------------" << endl;
		for (auto l:L){
			l.print();
			cerr << endl;	
		}
		#endif
		if (checkOK(L)){
			cout << "possible" << "\n";
			return 0;
		}
	}
	{
		vector<line> L;
		L.emplace_back((point){db(0),db(0)},(point){db(0),db(1)});
		L.emplace_back((point){db(-INF),db(1)},(point){db(-INF),db(0)});
		
		for (int i=1;i<=n;i++){
			gao1(L,b[i].x,b[i].y);
			gao2(L,a[i].x,a[i].y);
		}
		gao1(L,INF,INF);
		gao2(L,0,0);
		
		L=getHL(L);
		if (checkOK(L)){
			cout << "possible" << "\n";
			return 0;
		}
	}
	cout << "impossible" << "\n";
	return 0;
}

详细

Test #1:

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

input:

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

output:

possible

result:

ok single line: 'possible'

Test #2:

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

input:

4
1 1 2 2
1 3 2 4
3 1 4 2
3 3 4 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

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

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

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

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

4
0 1 1 1000000000
1 0 999999999 1
999999999 0 1000000000 999999999
2 999999999 999999999 1000000000

output:

possible

result:

ok single line: 'possible'

Test #6:

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

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 999999999 1000000000

output:

impossible

result:

ok single line: 'impossible'

Test #7:

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

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 1000000000 1000000000

output:

impossible

result:

wrong answer 1st lines differ - expected: 'possible', found: 'impossible'