QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202034#5155. Faster Than LightPhantomThresholdCompile Error//C++206.9kb2023-10-05 18:38:062023-10-05 18:38:06

Judging History

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

  • [2023-10-05 18:38:06]
  • 评测
  • [2023-10-05 18:38:06]
  • 提交

answer

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

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
	{
		if(abs((__float128)p*x.q)>1e36 or abs((__float128)q*x.p)>1e36)
		{
			return (__float128)p*x.q<(__float128)q*x.p;
		}
		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
	{
		if(abs((__float128)p*x.q)>1e36 or abs((__float128)q*x.p)>1e36)
		{
			return (__float128)p*x.q>(__float128)q*x.p;
		}
		return p*x.q>q*x.p;
	}
	inline bool operator != (const frac &x) const{return p*x.q!=q*x.p;}
};

typedef frac db;

const db INF=1e9;
const db eps=0;
int sign(db k){
	if (k>eps) return 1;
	else if (k<eps) return -1;
	return 0;	
}
int cmp(db k1,db k2)
{
	if(k1<k2)return -1;
	if(k1>k2)return 1;
	return 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);	
	}
	/*
	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=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();
	/*
	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;
	*/
	point O=getLL(L[0],L[1]);
	//*
	int fd=0;
	for (int i=0;i<sz;i++){
		int nxt=(i+1)%sz;
		db lim=INF*db(2);
		if (L[i][0].x>lim || L[i][0].x<-lim) continue;
		if (L[i][0].y>lim || L[i][0].y<-lim) continue;
		if (L[i][1].x>lim || L[i][0].x<-lim) continue;
		if (L[i][1].y>lim || L[i][0].y<-lim) continue;
		
		if (L[nxt][0].x>lim || L[nxt][0].x<-lim) continue;
		if (L[nxt][0].y>lim || L[nxt][0].y<-lim) continue;
		if (L[nxt][1].x>lim || L[nxt][0].x<-lim) continue;
		if (L[nxt][1].y>lim || L[nxt][0].y<-lim) continue;
		
		O=getLL(L[i],L[nxt]);
		fd=1;
		break;
	}
	if(not fd)
	{
		assert(0);
		//cout<<"possible"<<endl;
		exit(0);
	}
	//*/
	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)});
		
		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);
		/*
		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)});
		
		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;
}

Details

answer.code: In member function ‘bool frac::operator<(const frac&) const’:
answer.code:18:23: error: call of overloaded ‘abs(__float128)’ is ambiguous
   18 |                 if(abs((__float128)p*x.q)>1e36 or abs((__float128)q*x.p)>1e36)
      |                    ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:18:54: error: call of overloaded ‘abs(__float128)’ is ambiguous
   18 |                 if(abs((__float128)p*x.q)>1e36 or abs((__float128)q*x.p)>1e36)
      |                                                   ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code: In member function ‘bool frac::operator>(const frac&) const’:
answer.code:27:23: error: call of overloaded ‘abs(__float128)’ is ambiguous
   27 |                 if(abs((__float128)p*x.q)>1e36 or abs((__float128)q*x.p)>1e36)
      |                    ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:27:54: error: call of overloaded ‘abs(__float128)’ is ambiguous
   27 |                 if(abs((__float128)p*x.q)>1e36 or abs((__float128)q*x.p)>1e36)
      |                                                   ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/includ...