QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46515#3581. Ancient TowerspechpoAC ✓6039ms4068kbC++2019.7kb2022-08-29 22:39:422022-08-29 22:39:43

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-29 22:39:43]
  • Judged
  • Verdict: AC
  • Time: 6039ms
  • Memory: 4068kb
  • [2022-08-29 22:39:42]
  • Submitted

answer

#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
//acos返回0~pi,asin返回-pi/2~pi/2。axx系列精度不好,慎用
namespace geo_2d{
const double INF=1e18, PI=3.14159265358979323846, eps=1e-9;
struct V{  //向量及其运算是几何基础,点也可以用向量表示
    LL x, y;
    V():x(0),y(0){}
    V(const V &a){ *this=a; }
    V(const LL &a, const LL &b):x(a),y(b){}
    void read(){ scanf("%lld%lld", &x, &y); }
    void prLL(){ printf("%lld %lld\n", x, y); }
}O, corner(-1e6-PI, -1e6-2*PI);  //三个vector参数abc表示以a为顶点的角bac/cab
inline bool zero(const double &x){ return abs(x)<eps; }
inline bool equal(const double &a, const double &b){ return zero(a-b); }
inline bool less(const double &a, const double &b){ return a<b-eps; }  //更严格
inline bool greater(const double &a, const double &b){ return a>b+eps; }
LL pre(LL i, LL n){ return i==0?n-1:i-1; }
LL nxt(LL i, LL n){ return i==n-1?0:i+1; }
template <typename Iterator, typename Container>
Iterator pre(Iterator a, Container &S){
    return a==S.begin()?S.end():--a;
}
template <typename Iterator, typename Container>
Iterator nxt(Iterator a, Container &S){
    return ++a==S.end()?S.end():a;
}
inline LL sqr(const LL &x){ return x*x; }
inline bool cmp1(const V &a, const V &b){ return a.x<b.x; }
inline bool cmp2(const V &a, const V &b){ return a.y<b.y; }
inline bool cmp3(const V &a, const V &b){ return a.x>b.x||a.x==b.x&&a.y<b.y; }   //先x后y升序排序
inline bool cmp4(const V &a, const V &b){ return a.x<b.x||a.x==b.x&&a.y>b.y; }   //先x后y升序排序
struct cmp5{
    bool operator()(const V &a, const V &b){ return cmp3(a, b); }
};
struct cmp6{
    bool operator()(const V &a, const V &b){ return cmp4(a, b); }
};
inline V operator-(const V &a){ return V(-a.x, -a.y); }
inline V operator+(const V &a, const V &b){ return V(a.x+b.x, a.y+b.y); }
inline V operator-(const V &a, const V &b){ return V(a.x-b.x, a.y-b.y); }
inline V operator*(const LL &x, const V &a){ return V(a.x*x, a.y*x); }
inline V operator*(const V &a, const LL &x){ return V(a.x*x, a.y*x); }
inline V operator/(const V &a, const LL &x){ return V(a.x/x, a.y/x); }
inline bool operator==(const V &a, const V &b){ return a.x==b.x&&a.y==b.y;}
inline bool operator!=(const V &a, const V &b){ return !(a==b); }
inline LL operator*(const V &a, const V &b){ return a.x*b.x+a.y*b.y; }
inline LL operator^(const V &a, const V &b){ return a.x*b.y-a.y*b.x; }
inline double len(const V &a){ return sqrt(a.x*a.x+a.y*a.y); }
inline double dis(const V &a, const V &b){ return len(a-b); }
inline V c_wise(const V &a){ return V(a.y, -a.x); }
inline double S_tri(const V &a, const V &b, const V &c){ return abs((b-a)^(c-a))/2; }
inline LL S_tri2(const V &a, const V &b, const V &c){ return abs((b-a)^(c-a)); }
inline double S_iso(const LL &l, const double &theta){ return 0.5*l*l*sin(theta); }
inline double S_roundtable(const LL &r, const LL &R, const LL &h){  //圆台体积
    return PI*h*(sqr(r)+r*R+sqr(R))/3;
}
bool equal_sign(LL a, LL b){
    return a>0&&b>0||a<0&&b<0;
}
bool contra_sign(LL a, LL b){
    return a>0&&b<0||a<0&&b>0;
}
/*inline bool operator<(const V &a, const V&b){  //二元组排序
    return less(a.x, b.x)||(equal(a.x, b.x)&&less(a.y, b.y));
}*/
inline double angle(const LL &a, const LL &b, const LL &c){  //余弦定理
    return acos((sqr(b)+sqr(c)-sqr(a))/(2*b*c));
}
inline double angle(const V &a, const V &b){  //向量夹角
    if ((a^b)==0) return 0;
    return acos(a*b/len(a)/len(b));
}  //0~pi
inline double angle2(const V &a, const V &b){  //-pi~pi,叉乘决定符号,与向量顺序有关
    return (a^b)>=0?angle(a, b):-angle(a, b);
}
inline bool obtuse(const V &a, const V &b, const V &c){ return (b-a)*(c-a)<0; }  //∠bac
inline bool acute(const V &a, const V &b, const V &c){ return (b-a)*(c-a)>0; }
inline bool right(const V &a, const V &b, const V &c){ return (b-a)*(c-a)==0; }
struct L{  //记录单位方向向量+两点,也可以用来表示线段
    V d, a, b;
    L(){}
    L(const V &x1, const V &x2, const V &x3):d(x1),a(x2),b(x3){}
    L(const V &x, const V &y){ *this=L(y-x, x, y); }
    L(const V &d){ *this=L(d, V(0,0), d); }
};
inline L get_L(const V &d, const V &p){ return L(d, p, p+d); }
inline double angle(const V &v){  //从x轴开始算
    double tmp=atan2(v.y, v.x);
    return tmp>=0?tmp:tmp+2*PI;
}
inline double angle(const L &l){
    return angle(l.d);
}
inline bool on_line(const V &p, const L &l){
    return (l.d^(p-l.a))==0;
}
inline bool on_seg(const V &p, const L &l){
    return (dis(p, l.a)+dis(p, l.b)-dis(l.a, l.b))==0;
}
inline double dis(const V &p, const L &l){
    return 1.0*abs((p-l.a)^(p-l.b))/dis(l.a, l.b);
}
inline double dis2(const V &p, const L &l){  //带符号距离
    return 1.0*((p-l.a)^(p-l.b))/dis(l.a, l.b);
}
inline bool collinear(const V &a, const V &b){ return (a^b)==0; }
inline bool orthogonal(const V &a, const V &b){ return a*b==0; }
inline bool parallel(const L &l1, const L &l2){ return (l1.d^l2.d)==0; }
inline bool orthogonal(const L &l1, const L &l2){ return (l1.d*l2.d)==0; }
inline bool straddle(const L &l1, const L &l2){  //l1跨立在l2上
    LL f1=(l1.a-l2.a)^l2.d;
    LL f2=(l1.b-l2.a)^l2.d;
    if (f1*f2<=0) return true;
    else return false;
}
inline bool is_LLersect2(const L &l1, const L &l2){  //线与线段相交,l1为线
    LL a=(l2.a-l1.a)^l1.d, b=(l2.b-l1.a)^l1.d;
    if (a>=0&&b<=0) return true;
    if (a<=0&&b>=0) return true;
    return false;
}
inline bool is_LLersect(const L &l1, const L &l2){  //线段相交
    if ((min(l1.a.x, l1.b.x)>=max(l2.a.x, l2.b.x))||
        (max(l1.a.x, l1.b.x)<=min(l2.a.x, l2.b.x))||
        (min(l1.a.y, l1.b.y)>=max(l2.a.y, l2.b.y))||
        (max(l1.a.y, l1.b.y)<=min(l2.a.y, l2.b.y)))
            return false;
    //以上是快速排斥
    return straddle(l1, l2)&&straddle(l2, l1);
}  //先考虑l1跨立在l2上,再考虑l2跨立在l1上
//为方便操作直接传数组,以O为原点
inline double L_polygen(const V *a, const LL &n){
    double res=0;
    for (LL i=0; i<n; ++i) res+=dis(a[i], a[(i+1)%n]);
    return res;
}
inline LL S2_polygen(const V *a, const LL &n){
    LL res=0;
    for (LL i=0; i<n; ++i) res+=(a[i]^a[(i+1)%n]);
    return res;
}
inline void read_polygen(V *a, LL &n, bool with_n){
    if (with_n) scanf("%lld", &n);
    for (LL i=0; i<n; ++i) a[i].read();
}
inline void prLL_polygen(V *a, LL &n, bool with_n){
    if (with_n) printf("%lld\n", n);
    for (LL i=0; i<n; ++i) a[i].prLL();
}
inline bool is_convex(const V *a, const LL &n){
    LL j, k, d=0, nd; LL o;
    for (LL i=0; i<n; ++i){
        j=(i+1)%n, k=(i+2)%n;
        o=(a[j]-a[i])^(a[k]-a[j]);
        if (o==0) continue;
        nd=o<0?-1:1;
        if (!d) d=nd;
        else if (d!=nd) return false;
    }
    return true;
}
inline bool cmp(const V &a, const V &b){
    LL dot=(a-O)^(b-O);
    if (dot>0) return true;
    return false;
}
inline LL rshort(const V &a, const V &b){  //极角排序(找正确的基准点以极角为指标排序)比较函数
    LL dot=(a-O)^(b-O);
    if (dot>0) return 2;  //左返回0,等返回1,右返回2
    if (dot==0) return dis(a, O)<=dis(b, O);  //全共线情况
    return 0;
}
inline LL lshort(const V &a, const V &b){
    LL dot=(a-O)^(b-O);
    if (dot>0) return 0;  //左返回2,等返回1,右返回0
    if (dot==0) return dis(a, O)<dis(b, O);
    return 2;
}
inline bool in_poly(const V &p, const V *a, const LL &n){
    double x; LL j, res=0;
    for (LL i=0; i<n; ++i){
        j=(i+1)%n;
        if (a[i].y==a[j].y) continue;
        if (max(a[i].y, a[j].y)<p.y) continue;
        if (min(a[i].y, a[j].y)>=p.y) continue;
        x=a[i].x+1.0*(p.y-a[i].y)/(a[j].y-a[i].y)*(a[j].x-a[i].x);
        if (x<p.x) res^=1;
    }
    return res?true:false;
}
inline LL in_convex(const V &p, const V *a, const LL &n){  //已经去边界极角排序,满足a[0]在最下方
    O=a[0];
    if (lshort(a[1], p)||rshort(a[n-1], p)) return 0;
    LL x=upper_bound(a+1, a+n, p, cmp)-a-1;
    O=a[x];  //2包含 1在边上 0在凸包外
    return lshort(p, a[(x+1)%n]);
}
inline V find_lowest(V *a, const LL &n){
    LL id=0;
    for (LL i=0; i<n; ++i)
        if (a[i].y<a[id].y||
                a[i].y==a[id].y&&a[i].x<a[id].x) id=i;
    return a[id];
}
inline void polar_sort(V *a, const LL &n, const V &origin){
    O=origin;
    sort(a, a+n, rshort);  //以在右侧或者共线且距离小为小
    LL m;  //最后的共线部分要反转,以便边上点要保留的情况
    for (m=n-1; m>=0; --m) if (!((a[m]-a[0])^(a[n-1]-a[0]))) break;
    if (~m) reverse(a+m+1, a+n);  //如果是一条直线就不用反转了
    O=V(0, 0);
}
bool cmp_A(const V &a, const V &b){
    double a1=angle(a-O), a2=angle(b-O);
    return a1<a2||a1==a2&&dis(a, O)<dis(b, O);
}
inline void polar_sort2(V *a, const LL &n, const V &origin){  //真·极角排序
    O=origin;
    sort(a, a+n, cmp_A);
    O=V(0, 0);
}
inline bool turn_right(const V &p1, const V &p2, const V &p3){  //p1指向p2,p2指向p3,前面乘后面
    return ((p2-p1)^(p3-p2))<0;
}
inline bool turn_left(const V &p1, const V &p2, const V &p3){
    return ((p2-p1)^(p3-p2))>0;
}
inline bool turn_right2(const V &O, const V &A, const V &B){  //OA到OB
    return ((A-O)^(B-O))<0;
}
inline bool turn_left2(const V &O, const V &A, const V &B){
    return ((A-O)^(B-O))>0;
}
inline void graham(V *a, LL &n, bool include_on_edge){
    LL cnt=0, id1, id2;
    LL *s=new LL[n];
    for (LL i=0; i<=n; ++i){
        while (cnt>=2){
            id1=s[cnt-1]; id2=s[cnt-2];
            if (include_on_edge){
                if (a[id1]!=a[i%n]&&!turn_right(a[id2], a[id1], a[i%n])) break;
            } else if (turn_left(a[id2], a[id1], a[i%n])) break;
            if (i==n&&cnt==2) break;  //特判点都在一条直线上的情况
            --cnt;
        }
        if (i<n) s[cnt++]=i;
    }
    //if (a[s[0]]==a[s[cnt-1]]) cnt=1;  //特判只有一个点的情况,不出现重复点
    n=cnt;
    for (LL i=0; i<n; ++i) a[i]=a[s[i]];
    delete []s;
}
inline void andrew(V *a, LL &n, bool include_on_edge){
    LL cnt=0, id1, id2;
    LL *s=new LL[n];
    for (LL i=0; i<n; ++i){
        while (cnt>=2){
            id1=s[cnt-1]; id2=s[cnt-2];
            if (include_on_edge){
                if (!turn_right(a[id2], a[id1], a[i%n])) break;
            } else if (turn_left(a[id2], a[id1], a[i%n])) break;
            --cnt;
        }
        if (i<n) s[cnt++]=i;
    }
    n=cnt;
    for (LL i=0; i<n; ++i) a[i]=a[s[i]];
    delete []s;
}
inline void merge_2(V *a, LL &n, V *b, LL &m, V *c, LL &N){
    N=0;
    for (LL i=0; i<n; ++i) c[N++]=a[i];
    for (LL i=1; i<m-1; ++i) c[N++]=b[i];
}
inline void merge_convex(V *a, LL &n, V *b, LL &m, V *c, LL &N, bool include_on_edge, bool (*cmp)(const V &a, const V &b)){
    LL cnta=0, cntb=0; N=0;
    while (N<n+m){
        while ((cntb==m||cmp(a[cnta], b[cntb]))&&cnta<n) c[N++]=a[cnta++];
        while ((cnta==n||!cmp(a[cnta], b[cntb]))&&cntb<m) c[N++]=b[cntb++];
    }
    andrew(c, N, include_on_edge);
}
template <typename cmp> using Iter=typename multiset<V, cmp>::iterator;
template <typename cmp, typename Iter>
inline bool in_dynavex(Iter iter, multiset<V, cmp> &S){
    if (iter==S.begin()||iter==--S.end()) return false;
    if (!turn_left(*pre(iter, S), *iter, *nxt(iter, S))) return true;
    return false;
}
template <typename cmp>
inline bool in_dynavex(V &p, multiset<V, cmp>&S){
    auto iter=S.find(p);
    if (iter!=S.end()) return true;
    iter=S.insert(p);
    bool flag=in_dynavex(iter, S);
    S.erase(iter);
    return flag;
}
template <typename maLLain_type>  //对关于边的数据进行动态维护
inline void maLLain1(maLLain_type &obj, const V &a, const V &b){  //加边
    obj+=dis(a, b);
}
template <typename maLLain_type>
inline void maLLain2(maLLain_type &obj, const V &a, const V &b){  //删边
    obj-=dis(a, b);
}
template <typename cmp, typename maLLain_type>
inline void dynavex_insert(const V &p, multiset<V, cmp> &S, maLLain_type &obj){
    auto iter=S.insert(p);
    if (S.siz()==2) maLLain1(obj, *S.begin(), *++S.begin());
    if (S.siz()<3) return;
    if (in_dynavex(iter, S)){
        S.erase(iter);
        return;
    }
    if (iter!=S.begin()&&iter!=--S.end())
        maLLain2(obj, *pre(iter, S), *nxt(iter, S));
    if (iter!=S.begin()){
        maLLain1(obj, *pre(iter, S), *iter);
        while (pre(iter, S)!=S.begin()){
            auto iter2=pre(iter, S);
            auto iter3=pre(iter2, S);
            if (!turn_left(*iter3, *iter2, *iter)){
                maLLain2(obj, *iter2, *iter3);
                maLLain2(obj, *iter2, *iter);
                maLLain1(obj, *iter3, *iter);
                S.erase(iter2);
            }
            else break;
        }
    }
    if (iter!=--S.end()){
        maLLain1(obj, *nxt(iter, S), *iter);
        while (++nxt(iter, S)!=S.end()){
            auto iter2=nxt(iter, S);
            auto iter3=nxt(iter2, S);
            if (!turn_left(*iter, *iter2, *iter3)){
                maLLain2(obj, *iter2, *iter3);
                maLLain2(obj, *iter2, *iter);
                maLLain1(obj, *iter3, *iter);
                S.erase(iter2);
            }
            else break;
        }
    }
}
template <typename maLLain_type>
struct Dynavex{
    multiset<V, cmp5> upper;
    multiset<V, cmp6> lower;
    inline void insert(const V &p, maLLain_type &obj){
        dynavex_insert(p, upper, obj);
        dynavex_insert(p, lower, obj);
    }
    inline bool inside(const V &p){
        return in_dynavex(p, upper)&&in_dynavex(p, lower);
    }
};
inline double height(const V &a, const V &b1, const V &b2){  //b1、b2为底
    return S_tri(a, b1, b2)/dis(b1, b2);
}
inline double diameter(const V *a, const LL &n){
    double ans=0; LL j=0;
    for (LL i=0; i<n; ++i){  //枚举顶点,对面是平行线
        while (height(a[i], a[j], a[(j+1)%n])<height(a[i], a[(j+1)%n], a[(j+2)%n]))
            j=(j+1)%n;
        ans=max(ans, dis(a[i], a[j]));
        ans=max(ans, dis(a[i], a[(j+1)%n]));
    }
    return ans;
}
double max_dis(V *a, LL &n){  //最长距离点对(直径)
    graham(a, n, false);
    return diameter(a, n);
}
double min_dis(V *a, V *b, const LL &l, const LL &r){  //随着分治进行,对b要按y排序
    if (l+1==r) return INF;
    LL m=(l+r)>>1;
    double D=min(min_dis(a, b, l, m), min_dis(a, b, m, r));
    V *c=(V*)malloc(sizeof(V)*(r-l));
    V *d=(V*)malloc(sizeof(V)*(r-l));
    LL i=l, j=m, cnt=0;
    while (i<m||j<r){  //归并
        if (j==r||i<m&&b[i].y<b[j].y) c[cnt++]=b[i++];
        else c[cnt++]=b[j++];
    } cnt=0;
    L seperator(a[m], V(a[m].x, a[m].y+1));
    for (i=0; i<r-l; ++i) if (dis(c[i], seperator)<D) d[cnt++]=c[i];
    for (i=0; i<cnt-2; ++i)  //距离分割线在d内的点,按y坐标向后枚举两个
        D=min(D, min(dis(d[i], d[i+1]), dis(d[i], d[i+2])));
    D=min(D, dis(d[cnt-2], d[cnt-1]));
    memcpy(b+l, c, sizeof(V)*(r-l));
    free(c); free(d);
    return D;
}
double min_dis(V *a, const LL &n){  //最短距离点对
    sort(a, a+n, cmp1);
    V *b=(V*)malloc(sizeof(V)*n);
    memcpy(b, a, sizeof(V)*n);
    double ans=min_dis(a, b, 0, n);
    free(b);
    return ans;
}
void Minkowski_sum(V *a, LL n, V *b, LL m, V *c, LL &N){
    V *l=(V*)malloc((n+m)*sizeof(V)); N=0;
    LL cnta=0, cntb=0;
    V pa, pb;
    while (cnta<n||cntb<m){
        if (n) pa=a[(cnta+1)%n]-a[cnta];
        if (m) pb=b[(cntb+1)%m]-b[cntb];
        if (cnta==n){
            l[N++]=pb; cntb++;
            continue;
        }
        if (cntb==m){
            l[N++]=pa; cnta++;
            continue;
        }
        if ((pa^pb)>0) l[N++]=pa, cnta++;
        else if ((pa^pb)==0) l[N++]=pa+pb, cnta++, cntb++;
        else l[N++]=pb, cntb++;
    }
    if (!m) c[0]=a[0];
    else if (!n) c[0]=b[0];
    else c[0]=a[0]+b[0];  //最下面的点,一定是正好往右走  //可以先判一下
    for (LL i=0; i<N; ++i)
        c[i+1]=c[i]+l[i];
    free(l);
}
using pdd=pair<double, double>;
inline bool seg_LLersect(const pdd &a, const pdd &b){
    if (less(b.second, a.first)) return false;
    if (greater(b.first, a.second)) return false;
    return true;
}
inline void seg_add(pdd &a, const pdd &b){
    if (!seg_LLersect(a, b)) return;
    a.first=min(a.first, b.first);
    a.second=max(a.second, b.second);
}
inline bool seg_include(const pdd &a, const pdd &b){
    return a.first<=b.first&&a.second>=b.second;
}
}
using namespace geo_2d;

const LL maxn=405;
LL S, n, m, cnt, siz[maxn];
pair<LL, LL> area[maxn];
V a[maxn], b[maxn];
LL A[maxn], B[maxn], cnta, cntb;
struct Bit{
    LL a[maxn], n, q[maxn*10], m;
    inline LL lowbit(LL x){ return x&(-x); }
    Bit(){};
    Bit(LL N){ n=N; }
    inline void clear(){
        for (LL i=0; i<m; ++i)
            a[q[i]]=0;
        m=0;
    }
    inline void modify(LL x, LL d){
        while (x<=n){
            if (!a[x]) q[m++]=x;
            a[x]+=d;
            x+=lowbit(x);
        }
    }
    inline LL query(LL x){
        LL ans=0;
        while (x){
            ans+=a[x];
            x-=lowbit(x);
        }
        return ans;
    }
    inline LL query(LL l, LL r){
        return query(r)-query(l-1);
    }
}bit;

int main(){
    scanf("%lld", &S); S*=2;
    read_polygen(a, n, true);
    bit.n=n;
    V d, t; LL ans=0;
    for (LL i=0; i<n; ++i)
        for (LL j=i+1; j<n; ++j){
            cnta=cntb=0;
            d=a[j]-a[i];
            for (LL k=0; k<n; ++k){
                if (k==i||k==j) continue;
                t=a[k]-a[i];
                if ((d^t)<0) A[cnta++]=S_tri2(a[i], a[j], a[k]);
                else B[cntb++]=S_tri2(a[i], a[j], a[k]);
            }
            if (!cnta||!cntb) continue;
            sort(B, B+cntb);
            for (int k=0; k<cnta; ++k)
                ans+=B+cntb-lower_bound(B, B+cntb, S-A[k]);
        }
    for (LL i=0; i<n; ++i){
        m=0;
        for (LL j=0; j<n; ++j) if (i!=j) b[m++]=a[j];
        polar_sort2(b, n-1, a[i]);
        for (LL j=0; j<n-1; ++j){  //枚举对角线
            LL p1=nxt(j, n-1), p2=nxt(j, n-1);
            while (turn_left2(a[i], b[j], b[p2])&&p2!=j)
                p2=nxt(p2, n-1);
            if (turn_right2(a[i], b[j], b[p1])) continue;
            if (p2==j) continue;
            cnt=0;
            for (LL k=p1; k!=j; k=nxt(k, n-1)){
                if (turn_left2(a[i], b[j], b[k]))
                    area[cnt++]=make_pair(S-S_tri2(a[i], b[j], b[k]), k);
                else area[cnt++]=make_pair(S_tri2(a[i], b[j], b[k]), k);
            }
            sort(area, area+cnt, std::greater<pair<LL, LL>>());  //以面积大为小,方便查询
            for (int i=0; i<cnt; ++i) siz[area[i].second]=i+1;
            /*for (LL k=p1; k!=j; k=nxt(k, n-1)){
                if (turn_left2(a[i], b[j], b[k]))
                    siz[k]=lower_bound(area, area+cnt, S-S_tri2(a[i], b[j], b[k]),
                        std::greater<LL>())-area+1;
                else siz[k]=lower_bound(area, area+cnt, S_tri2(a[i], b[j], b[k]),
                        std::greater<LL>())-area+1;
            }*/
            bit.clear();
            while (turn_left(a[i], b[j], b[p1])){
                while (p2!=j&&angle(b[p1]-a[i], b[j]-a[i])+angle(b[p2]-a[i], b[j]-a[i])>=PI){
                    bit.modify(siz[p2], 1);
                    p2=nxt(p2, n-1);
                }
                ans+=bit.query(siz[p1]);
                p1=nxt(p1, n-1);
            }
        }
    }
    printf("%lld\n", ans/2);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3508kb

input:

2 4
1 2
3 4
3 3
4 1

output:

2

result:

ok single line: '2'

Test #2:

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

input:

4314 26
1569 1513
1454 1067
122 1333
1065 1429
1032 577
1159 955
587 1231
118 1270
1621 1536
512 871
698 1113
19 137
268 940
492 929
96 1077
292 174
661 1131
1056 239
742 194
1057 974
1604 1523
124 723
315 900
897 1236
469 477
1085 1189

output:

25417

result:

ok single line: '25417'

Test #3:

score: 0
Accepted
time: 39ms
memory: 3644kb

input:

5965 76
1251 145
1786 963
1570 61
1653 264
91 1726
695 934
743 1150
619 405
243 1862
1721 1044
838 1125
125 987
1203 910
1627 393
1553 859
1010 918
1188 1798
977 1835
1446 675
158 481
1808 1417
1144 276
788 1834
697 920
778 1010
618 1229
1359 652
58 597
452 208
1457 1120
1081 675
636 1180
914 538
15...

output:

2142660

result:

ok single line: '2142660'

Test #4:

score: 0
Accepted
time: 1401ms
memory: 3684kb

input:

1 250
317585868 598152434
843773388 209824234
92263069 613343638
590616991 779389536
116195475 274286318
290397390 898992827
50266020 818254190
627104042 754661662
336582604 62711465
95657793 175801878
452170674 298288603
966795197 10639394
791949036 803586958
201721863 62682611
772808232 475871864
...

output:

257344298

result:

ok single line: '257344298'

Test #5:

score: 0
Accepted
time: 1401ms
memory: 3756kb

input:

1000 250
489909807 579157286
426974190 974851864
351232834 414620104
391171962 367547122
311733897 568131259
671852560 798180643
450291034 329717374
564801347 64208901
522900708 569058854
747496171 165286265
364729854 440961125
42573807 338449743
752445471 558080018
195329229 256606629
388417588 393...

output:

258359224

result:

ok single line: '258359224'

Test #6:

score: 0
Accepted
time: 1408ms
memory: 3644kb

input:

1000000 250
941215258 343282149
682958157 715880819
517644744 497183549
859346949 977273175
940346170 218118245
91625396 464321762
648792552 562719601
721515059 964378174
422796415 202406046
353671885 383976556
636972702 45133308
145678370 401457239
475059265 752421732
674466339 50424707
864771350 2...

output:

260650430

result:

ok single line: '260650430'

Test #7:

score: 0
Accepted
time: 1381ms
memory: 3576kb

input:

100000000000 250
101624314 159623553
153687593 122892370
233790285 234784657
426866037 277531011
387784199 201308854
748358468 3428305
201922674 774144670
481611426 971908533
367035225 423292377
259088766 211506135
318942549 175802255
917757628 328812367
204268050 861194486
621660803 662766622
20447...

output:

257000024

result:

ok single line: '257000024'

Test #8:

score: 0
Accepted
time: 881ms
memory: 3648kb

input:

128 250
87940 490622755
844625 470949830
1360527 463139767
1542565 460754799
3565033 440398624
4286283 434670747
7546740 413456442
9387580 403566324
9994703 400527341
12551094 388673614
13793262 383368062
15540302 376311676
20451785 358460216
27642495 336053705
36346955 312848044
42249640 298841831
...

output:

158882750

result:

ok single line: '158882750'

Test #9:

score: 0
Accepted
time: 884ms
memory: 3644kb

input:

1000000000000 250
74316 491379590
2172584 453439667
3563944 440407695
4252955 434924140
5885704 423507761
11258282 394493917
22610880 351340562
23248466 349308344
27064687 337728036
29093863 331930340
32426158 322870944
37313956 310469989
39123895 306110299
40360287 303197219
51224833 279543995
7262...

output:

158882596

result:

ok single line: '158882596'

Test #10:

score: 0
Accepted
time: 892ms
memory: 4064kb

input:

1000000000000000 250
1999 498585909
86254 490713066
364512 480911278
717767 473218431
2917554 446064464
28615316 333277234
31196560 326151400
37660724 309625645
40743604 302304367
52693714 276578679
57149865 267871245
64676503 254045831
64986137 253498601
73177329 239572643
73185710 239558907
764001...

output:

158690301

result:

ok single line: '158690301'

Test #11:

score: 0
Accepted
time: 5957ms
memory: 3692kb

input:

1 400
467526769 85195364
225672739 676874691
482779579 401136887
842924424 883009585
695094694 16970951
127866211 667087790
348796082 450340214
758113817 947053867
50859403 422719383
484509644 744417132
525901816 509623389
342643408 286087025
339829212 216954812
925876339 274973537
740209606 7562305...

output:

1717879706

result:

ok single line: '1717879706'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

1 4
1 2
3 4
3 3
4 1

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 5980ms
memory: 3692kb

input:

100000000000000 400
380714483 121012358
754639896 374212230
251499688 914785718
304426117 493721170
648093554 223992706
636369399 132682333
405088289 752182289
656813997 658920273
266851901 664445919
692050240 567918329
667813809 704320804
773813959 603467078
766217868 969675946
479449900 307909031
...

output:

1695084992

result:

ok single line: '1695084992'

Test #14:

score: 0
Accepted
time: 5982ms
memory: 3672kb

input:

10000000 400
580695944 192753382
937895019 137397468
390252822 523406369
982122005 569014908
200988937 5989403
145078052 899491855
606826411 803166147
966562503 945153639
748006339 640561259
424430815 433294206
276733249 889483881
663438442 358661637
742918074 262349148
189748187 519434585
511863931...

output:

1676593188

result:

ok single line: '1676593188'

Test #15:

score: 0
Accepted
time: 6039ms
memory: 3652kb

input:

1400434 400
53751349 97477045
310204931 125239024
369742886 808554246
579714188 367660695
378859868 573460506
908899666 159398706
522170854 728188301
958134200 151674089
315323856 944510256
242333635 209656437
830160729 705204733
958202640 984858268
577761247 712628528
37506279 478164604
355539048 6...

output:

1697561644

result:

ok single line: '1697561644'

Test #16:

score: 0
Accepted
time: 5944ms
memory: 3908kb

input:

10000 400
996609018 505810866
214183081 251635386
709268177 112304605
73830539 236945177
452391147 309229299
79768211 481923079
844749319 965243603
364472947 173236695
265534912 61419527
360623062 896888897
851741353 252319248
814864031 987082658
981912301 20545573
890090827 150513184
827242596 4610...

output:

1685812686

result:

ok single line: '1685812686'

Test #17:

score: 0
Accepted
time: 5931ms
memory: 3640kb

input:

10010 400
516735939 553106692
890223632 284242609
18974994 939328370
50066856 18053211
46277717 854942078
50330486 184445579
798012040 803346910
204171736 30696286
650486690 729301542
830815134 561605913
465213728 771175096
632289323 630366465
232861648 548220307
430645723 334466338
353796222 241827...

output:

1706903950

result:

ok single line: '1706903950'

Test #18:

score: 0
Accepted
time: 5977ms
memory: 3692kb

input:

10000000 400
791559755 728793923
92037253 880096143
8427433 624970639
919700463 21453086
194307614 18931032
494247451 372482124
61387912 352841935
317275458 6622899
648068020 993901805
727090562 356208771
236083096 634624025
595529501 692789111
980738959 251376808
935744668 327137643
51021009 642836...

output:

1683868754

result:

ok single line: '1683868754'

Test #19:

score: 0
Accepted
time: 5933ms
memory: 3752kb

input:

1000012341 400
846580774 376779176
119449172 758044568
71746587 70705427
430552563 284033019
79315691 670109747
481965709 581064071
453381439 990950986
528555866 572697188
989259359 109786938
135179607 420627391
344497211 769574973
612914473 513812777
293424153 762274117
686490297 854941395
56500473...

output:

1680918602

result:

ok single line: '1680918602'

Test #20:

score: 0
Accepted
time: 5934ms
memory: 4068kb

input:

1000000000000000000 400
606198357 9925234
607356611 30504202
448275416 776381334
806632151 85429027
391625941 281930407
45916121 618962261
308227945 444162800
639228228 470344940
420290106 560455339
41749802 67831866
153968729 82178563
255385736 622775750
853688028 560309693
197262244 114483728
5386...

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 5947ms
memory: 3656kb

input:

142 400
98627 50502
92610 44300
49410 45941
89508 50351
41314 77088
16068 91491
26303 44998
46623 86154
84015 41296
2313 81223
76303 17007
53850 47688
18060 94553
5476 93120
7269 96627
24889 9413
518 15885
75802 40475
60582 81522
36450 29313
10034 53032
23950 52968
342 12010
40099 94836
54282 83632
...

output:

1694281814

result:

ok single line: '1694281814'

Test #22:

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

input:

128 400
72449 491488600
653498 474444743
904203 469943626
1499057 461311367
1814375 457443167
2491230 450149978
3878592 437842544
4083632 436227305
4451148 433431723
4872147 430369475
6469804 419825528
7603033 413136729
7982396 411013044
9136446 404852894
9938222 400805975
10125900 399883237
1037223...

output:

1050739900

result:

ok single line: '1050739900'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

4 5
1 1
3 3
3 0
0 1
1 0

output:

3

result:

ok single line: '3'

Test #24:

score: 0
Accepted
time: 3729ms
memory: 3688kb

input:

112389123 400
11746 496572707
44010 493366069
135596 488356203
1382973 462837371
1594879 460095918
2417874 450887591
6116772 422029763
6504141 419614440
6587129 419106618
7409315 414242100
7663842 412792731
8483413 408286068
9627384 402354223
13271106 385566682
16257334 373536432
17056508 370518018
...

output:

1050739900

result:

ok single line: '1050739900'

Test #25:

score: 0
Accepted
time: 2460ms
memory: 3748kb

input:

128 350
86843 490681410
2915032 446087708
3187793 443629513
5167309 428301963
10467574 398225717
18101330 366682062
22440269 351889555
26133020 340469169
29330693 331268247
29838053 329859633
33443623 320208044
35159561 315817029
35318797 315415656
47708501 286851225
55489891 271066027
57452172 2672...

output:

614597725

result:

ok single line: '614597725'

Test #26:

score: 0
Accepted
time: 2478ms
memory: 3800kb

input:

128129123481 350
73606 491420902
885312 470258972
2635647 448729143
2817083 446998604
5217365 427957343
5763571 424300906
7626234 413005317
8800294 406603802
11436463 393671873
12072236 390791493
14331191 381147956
14504061 380443762
16647823 372052065
18948962 363655218
20132752 359545647
20334777 ...

output:

614597648

result:

ok single line: '614597648'

Test #27:

score: 0
Accepted
time: 1551ms
memory: 3688kb

input:

12831 300
49128 492991004
901834 469982981
4309383 434495700
4620550 432182591
5548428 425719157
6216086 421403266
7727344 412434983
9577645 402604341
21571352 354720856
25037060 343762341
30839589 327117064
31723948 324735801
41852105 299748891
43932660 295054686
45399342 291821608
45894945 2907427...

output:

330791175

result:

ok single line: '330791175'

Test #28:

score: 0
Accepted
time: 1539ms
memory: 3668kb

input:

1231198212341 300
364162 480920422
628161 474944715
870281 470512298
2442462 450639119
3220861 443338834
4167735 435576672
4563839 432598140
8743883 406900978
10480691 398162648
11225189 394647331
11526077 393260939
11553424 393135867
13377265 385116084
14762605 379398709
17501447 368869732
20515223...

output:

330790448

result:

ok single line: '330790448'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3592kb

input:

1 4
0 0
1000 0
0 1000
1000 1000

output:

1

result:

ok single line: '1'

Test #30:

score: 0
Accepted
time: 11ms
memory: 3724kb

input:

8408 49
1492 1850
761 591
536 399
1943 1555
294 2079
1846 1514
1753 1551
782 1184
191 1164
975 438
315 1938
582 680
282 1370
489 105
957 1966
1722 1780
1089 1853
934 549
266 385
664 836
1234 1899
950 989
866 1995
116 1495
169 187
1484 419
1946 1822
1117 1444
976 1371
2108 1827
1582 450
1616 1846
492...

output:

335537

result:

ok single line: '335537'

Test #31:

score: 0
Accepted
time: 4ms
memory: 3812kb

input:

6424 31
2642 826
1979 2024
1468 758
1651 1649
2827 1185
807 1544
2910 390
1678 2036
2369 2422
1007 2712
1506 2640
1619 394
704 2858
903 1096
1705 220
2358 1248
2148 2430
1298 2708
1707 966
770 2087
2462 131
1308 780
1662 1351
866 1185
24 1093
1762 1305
1629 185
2460 1291
2422 2481
631 1422
670 2774

output:

51002

result:

ok single line: '51002'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

7715 33
2788 2333
2106 2760
3132 1162
712 3009
2475 2869
62 3164
1967 1449
2067 438
300 3153
2416 809
1608 476
2791 927
1322 1472
1269 1094
1106 1466
2771 591
3049 2433
1384 711
2625 753
654 1999
3315 983
978 2924
2326 1497
3297 1134
2319 128
1786 776
1654 1032
1193 281
1772 3232
208 1085
980 2523
3...

output:

65127

result:

ok single line: '65127'

Test #33:

score: 0
Accepted
time: 42ms
memory: 3616kb

input:

8141 79
2997 1721
1062 1408
2797 1835
1902 3586
1370 1205
3841 3654
711 2666
3131 3767
38 2244
3331 700
1804 3170
2342 3632
2731 2428
1550 3358
3848 1123
2616 3252
3082 2362
3279 661
1741 910
125 600
3317 2124
1667 1023
1319 2706
156 1499
2948 3652
238 2960
1573 155
1733 681
3221 828
3518 2688
1134 ...

output:

2456415

result:

ok single line: '2456415'

Test #34:

score: 0
Accepted
time: 52ms
memory: 3932kb

input:

1897 84
1351 810
554 1362
618 423
965 1497
948 140
1885 819
993 1539
694 2280
1195 175
2191 950
1687 670
575 2093
1688 198
1808 1779
1379 1808
194 465
829 1229
952 1130
1310 461
1148 756
2087 2151
225 582
2086 769
401 1381
1469 76
2176 331
916 89
1878 305
0 2076
2057 1346
2248 1208
585 1032
2202 180...

output:

3113918

result:

ok single line: '3113918'