QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270960#5155. Faster Than Lightucup-team173WA 0ms43408kbC++203.2kb2023-12-01 18:57:532023-12-01 18:57:54

Judging History

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

  • [2023-12-01 18:57:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:43408kb
  • [2023-12-01 18:57:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define mpr make_pair
#define pb push_back
#define fi first
#define se second
#define db double

#define y1 askdjfa
#define y2 asdkjhfa
#define x1 klsadjfa
#define x2 lkdjfa
const int maxn=211111;

const db eps=1e-15;

int x1[maxn],y1[maxn],x2[maxn],y2[maxn];
int n;
struct vec{
    db x,y;
    vec(db _x=0,db _y=0){
        x=_x,y=_y;
    }
    friend vec operator +(const vec&a,const vec&b){
        return vec(a.x+b.x,a.y+b.y);
    }
    friend vec operator -(const vec&a,const vec&b){
        return vec(a.x-b.x,a.y-b.y);
    }
    friend db operator *(const vec&a,const vec&b){
        return a.x*b.y-a.y*b.x;
    }
    friend vec operator *(const vec&a,const db&b){
        return vec(a.x*b,a.y*b);
    }
    void print(){
        cout<<"("<<x<<","<<y<<")";
    }
};
struct line{
    vec s,t;
    db a;
    void geta(){
        a=atan2(t.y-s.y,t.x-s.x);
    }
    void print(){
        cout<<"[";s.print();
        cout<<"to";
        t.print();
        cout<<"]";
    }
};
line ln[maxn<<1],q[maxn<<1];
vec p[maxn<<1];
int lncnt;
int xl,yl,xr,yr;
bool left(vec p,line l){
    return (l.t-l.s)*(p-l.s)>0;
}
vec pos(line a,line b){
    vec x=a.s-b.s;
    db t=((b.t-b.s)*x)/((a.t-a.s)*(b.t-b.s));
    return a.s+(a.t-a.s)*t;
}
int check(){
    for(int i=1;i<=lncnt;i++)ln[i].geta();
    sort(ln+1,ln+lncnt+1,[&](line a,line b){
        return a.a<b.a;
    });
    int h=1,t=1;
    q[1]=ln[1];
    // for(int i=1;i<=lncnt;i++){
    //     ln[i].print();cout<<"\n";
    // }
    for(int i=2;i<=lncnt;i++){
        while(h<t&&!left(p[t-1],ln[i]))t--;
        while(h<t&&!left(p[h],ln[i]))h++;
        if(fabs(q[t].s*ln[i].s)<eps)q[t]=left(q[t].s,ln[i])?q[t]:ln[i];
        else q[++t]=ln[i];
        if(h<t)p[t-1]=pos(q[t],q[t-1]);
    }
    while(h<t&&!left(p[t-1],q[h]))t--;
    p[t]=pos(q[t],q[h]);
    if(t-h<=1)return 0;
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;    
    xl=yl=-2e9;
    xr=yr=2e9;
    for(int i=1;i<=n;i++){
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        xl=max(xl,x1[i]);
        xr=min(xr,x2[i]);
        yl=max(yl,y1[i]);
        yr=min(yr,y2[i]);
    }
    if(xl<=xr||yl<=yr)cout<<"possible\n",exit(0);
    lncnt=0;
    for(int i=1;i<=n;i++){
        ln[++lncnt]=(line){vec(1,y2[i]-x1[i]+eps * 10),vec(0,y2[i]+eps * 10)};
        ln[++lncnt]=(line){vec(0,y1[i]-eps * 10),vec(1,y1[i]-x2[i]-eps * 10)};
    }
    ln[++lncnt]=(line){vec(0,1e9),vec(0,-1e9)};
    ln[++lncnt]=(line){vec(0,-1e9),vec(1e9,-1e9)};
    ln[++lncnt]=(line){vec(1e9,-1e9),vec(1e9,1e9)};
    ln[++lncnt]=(line){vec(1e9,1e9),vec(0,1e9)};
    if(check())cout<<"possible\n",exit(0);
    lncnt=0;
    for(int i=1;i<=n;i++){
        ln[++lncnt]=(line){vec(1,y2[i]-x2[i]+eps * 10),vec(0,y2[i]+eps * 10)};
        ln[++lncnt]=(line){vec(0,y1[i]-eps * 10),vec(1,y1[i]-x1[i]-eps * 10)};
    }
    ln[++lncnt]=(line){vec(-1e9,1e9),vec(-1e9,-1e9)};
    ln[++lncnt]=(line){vec(-1e9,-1e9),vec(0,-1e9)};
    ln[++lncnt]=(line){vec(0,-1e9),vec(0,1e9)};
    ln[++lncnt]=(line){vec(0,1e9),vec(-1e9,1e9)};
    if(check())cout<<"possible\n",exit(0);    
    cout<<"impossible";
    return 0;
}

详细

Test #1:

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

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: -100
Wrong Answer
time: 0ms
memory: 43408kb

input:

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

output:

possible

result:

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