QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876058#7653. Balloon DartsSeptemperWA 1ms3712kbC++233.3kb2025-01-30 16:42:002025-01-30 16:42:01

Judging History

This is the latest submission verdict.

  • [2025-01-30 16:42:01]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3712kb
  • [2025-01-30 16:42:00]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using ld =long long;
const int N=1e5;
const ld eps=1e-10;

ld sqr(ld x) {return x*x;}
struct point{
	ld x,y;
	point operator + (const point &a) const{
		return {x+a.x,y+a.y};
	}
	point operator - (const point &a) const{
		return {x-a.x,y-a.y};
	}
	point operator * (const ld a) const{
		return {x*a,y*a};
	}
	point operator / (const ld a) const{
		return {x/a,y/a};
	}
	point rotate (ld t) const{
		return {x*cos(t)-y*sin(t),
			    x*sin(t)-y*cos(t)};
	}
	point rot90() const{
		return {-y,x};
	}
	point unit() const{
		return *this/sqrt(sqr(x)+sqr(y));
	}
};
ld dis(const point &a,const point &b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
ld dot(const point &a,const point &b){
	return a.x*b.x+a.y*b.y;
}
ld det(const point &a,const point &b){
	return a.x*b.x-a.y*b.y;
}
int sgn(ld x){
	return x>eps ? 1:( x<-eps ? -1: 0);
}
bool turn_left(const point& a,const point &b,const point &c){
	return sgn(det(b-a,c-a))>0;
}
struct line{
	point s,t;
};
bool same_dir(const line &a,const line &b){
	return sgn(det(b.t-b.s,a.t-a.s))==0 && sgn(dot(b.t-b.s,a.t-a.s))>0;
}
bool operator == (const point &a,const point &b){
	return sgn(dot(a-b,a-b))==0;
}
bool point_on_segment(const point &a,const line &l){
	return sgn(det(l.s-a,a-l.t)) == 0 && sgn(dot(l.s-a,a-l.t)) <=0;
}
bool twoside(const point &a,const point &b,const line &c){
//	if(turn_left(c.s,c.t,a) && !turn_left(c.s,c.t,b)){
//		return 1;
//	}
//	else return 0;
	return sgn(det(a-c.s,c.t-c.s)) * sgn(det(b-c.s,c.t-c.s))<0;
}
bool inter_judge(const line &a,const line &b){
	if(point_on_segment(a.s,b) 
	|| point_on_segment(a.t,b)
	|| point_on_segment(b.s,a) 
	|| point_on_segment(b.t,a))
	return true;
	return twoside(a.s,a.t,b) && twoside(b.s,b.t,a);
}
point line_intersect(const line &a,const line &b){
	ld u=det(a.t-a.s,b.s-a.s);
	ld v=det(a.t-a.s,b.t-a.s);
	return (b.s*v+b.t*u)/(v+u);
}
ld point_to_line(const point &a,const line &l){
	return det(l.t-l.s,a-l.s) / dis(l.t,l.s);
}
ld point_to_segment(const point&a,const line &l){
	if(sgn(det(a-l.s,l.s-l.t))*sgn(det(a-l.t,l.s-l.t))<=0) return point_to_line(a,l);
	else return min(dis(a,l.s),dis(a,l.t));
}
vector<point>check(point &a,point &b,vector<point>&c){
	vector<point>num;
	for(int i=0;i<c.size();i++){
		if(c[i]==a || c[i]==b) continue;
		else {
			if((a.y-b.y)*(c[i].x-b.x)==(c[i].y-b.y)*(a.x-b.x))
			    continue;
		    else num.push_back(c[i]);
		}
	}
	return num;
}
bool sol(point &a,point &b,int k,vector<point>&c){
	auto num=check(a,b,c);
	if(num.size()){
		if(k*2>=num.size()) return 1;
		else if(k==0) return 0;
		else {
			for(int i=1;i<=k+1;i++){
				for(int j=i+1;j<=k+1;j++){
					if(sol(c[i],c[j],k-1,num)) return 1;
				}
			}
			return 0;
		}
	}
	else return 1;
}
inline void solve() {
	int n; cin >> n;
	int k=3;
	vector<point>a(n+1);
	for(int i=1;i<=n;i++) cin >> a[i].x >> a[i].y;
	if(n<=6) cout << "possible";
	else {
		for(int i=1;i<=k+1;i++){
			for(int j=i+1;j<=k+1;j++){
				if(sol(a[i],a[j],2,a)) {cout << "possible";return;}
			}
		}
		cout << "impossible";
	}
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
//	std::cin >> T;
	while (T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
0 0
1 1
2 4
3 9
4 16
5 25

output:

possible

result:

ok single line: 'possible'

Test #2:

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

input:

7
0 0
1 1
2 4
3 9
4 16
5 25
6 36

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

7
-1 -1
0 0
1 1
2 4
3 9
4 16
5 25

output:

possible

result:

ok single line: 'possible'

Test #4:

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

input:

15
0 0
1 1
5 5
17 17
1000000000 1000000000
-1000000000 -1000000000
1 0
2 0
4 0
8 0
16 0
32 0
64 0
64 1
64 2

output:

impossible

result:

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