QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#876058 | #7653. Balloon Darts | Septemper | WA | 1ms | 3712kb | C++23 | 3.3kb | 2025-01-30 16:42:00 | 2025-01-30 16:42:01 |
Judging History
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;
}
详细
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'