QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201865#5155. Faster Than LightPhantomThreshold#WA 1ms5540kbC++205.4kb2023-10-05 17:09:532023-10-05 17:09:53

Judging History

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

  • [2023-10-05 17:09:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5540kb
  • [2023-10-05 17:09:53]
  • 提交

answer

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

typedef long double db;
const db INF=1e9;
const db eps=1e-6;
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){0-y,x};
	}
	db abs2(){
		return x*x+y*y;	
	}
	int getP() const{
		return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);	
	}
	void print(){
		cerr << "(" << x << "," << 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;	
}
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];}
	void print(){
		p[0].print();
		cerr << "-> ";
		p[1].print();
		cerr << " ";
	}
};
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));	
}
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=200000;
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();
	point O=(point){db(0),db(0)};
	for (int i=0;i<sz;i++){
		int nxt=(i+1)%sz;
		O=O+getLL(L[i],L[nxt]);
	}
	O=O/sz;
	for (int i=0;i<sz;i++){
		if (sign(cross(L[i][1]-L[i][0],O-L[i][0]))<0) 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)});
		L.emplace_back((point){db(0),db(-INF*INF)},(point){db(1),db(-INF*INF)});
		L.emplace_back((point){db(1),db(INF*INF)},(point){db(0),db(INF*INF)});
		
		for (int i=1;i<=n;i++){
			gao1(L,a[i].x,b[i].y);
			gao2(L,b[i].x,a[i].y);
		}
		/*
		cerr << "----------------" << endl;
		for (auto l:L){
			l.print();
			cerr << endl;	
		}
		*/
		L=getHL(L);
		/*
		cerr << "----------------" << endl;
		for (auto l:L){
			l.print();
			cerr << endl;	
		}
		*/
		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)});
		L.emplace_back((point){db(0),db(-INF*INF)},(point){db(1),db(-INF*INF)});
		L.emplace_back((point){db(1),db(INF*INF)},(point){db(0),db(INF*INF)});
		
		for (int i=1;i<=n;i++){
			gao1(L,b[i].x,b[i].y);
			gao2(L,a[i].x,a[i].y);
		}
		L=getHL(L);
		if (checkOK(L)){
			cout << "possible" << "\n";
			return 0;
		}
	}
	cout << "impossible" << "\n";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5488kb

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: 5492kb

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: 5488kb

input:

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

output:

possible

result:

ok single line: 'possible'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5540kb

input:

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

output:

possible

result:

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