Ideone.com

download

copy

/***********Template Starts Here***********/
#include <bits/stdc++.h>
 
#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod)x-=mod;
 
using namespace std;
 
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;
 
const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;
 
 
/***********Template Ends Here***********/
struct {
    int n;
}_g;
pll point[1010];
 
vlong getArea ( int a, int b, int c ) {
    if ( b >= _g.n ) b -= _g.n;
    if ( c >= _g.n ) c -= _g.n;
    vlong res = point[a].ff * point[b].ss + point[b].ff * point[c].ss + point[c].ff * point[a].ss;
    res -= point[a].ff * point[c].ss + point[b].ff * point[a].ss + point[c].ff * point[b].ss;
    return ABS(res);
}
 
int mxlimit[1010][1010];
 
int binarySearch ( int i, int j, int m , int n, vlong k ) {
 
    ///First search between  (j + 1) - m
    int low = j + 1, high = m;
 
    ///Upper Bound
    while ( low <= high ) {
        int mid = ( low + high ) / 2;
 
        vlong a = getArea( i, j, mid );
 
        if ( a <= k ) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
 
    int res = ( low - j - 1 );
 
    ///Now search between m+1 - (n-1)
    m = MAX(m+1,j+1);
 
    if ( m >= n ) return res; ///No more segment
 
    low = m; high = n - 1;
 
    ///Lower Bound
    while ( low <= high ) {
        int mid = ( low + high ) / 2;
 
        vlong a = getArea( i, j, mid );
 
        if ( a <= k ) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
 
    res += ( n - 1 ) - low + 1;
 
    return res;
}
 
int main () {
    #ifdef forthright48
    freopen ( "input.txt", "r", stdin );
    //freopen ( "output.txt", "w", stdout );
    #endif // forthright48
 
    int kase;
    scanf ( "%d", &kase );
 
    while ( kase-- ) {
        int n;
        vlong lim;
        scanf ( "%d %lld", &n, &lim );
        lim *= 2;
        _g.n = n;
 
        FOR(i,0,n-1){
            scanf ( "%lld %lld", &point[i].ff, &point[i].ss );
        }
 
        if ( n <= 2 ) {
            printf ( "0\n" );
            continue;
        }
 
 
        ///Find the point which gives maximum area for given points (i,j)
        FOR(i,0,n-1){
            int s = i + 1; ///Initiate two pointer
            vlong prev = 0;
            FOR(f,i+1,n-1){
                prev = getArea( i, f, s );
                ///Make s go forward as much as possible
                while ( 1 ) {
                    if ( s + 1 >= n ) break; ///Not possible to go forward
                    vlong cur = getArea( i, f, s + 1 );
                    if ( cur >= prev ) {
                        prev = cur;
                        s++;
                    }
                    else break;
                }
 
                mxlimit[i][f] = s;
            }
        }
 
        vlong res = 0;
 
        ///Binary Search
        FOR(i,0,n-3){
            FOR(j,i+1,n-2){
                int m = mxlimit[i][j];
                res += binarySearch ( i, j, m, n, lim );
            }
        }
 
        printf ( "%lld\n", res );
    }
 
    return 0;
}

LyoqKioqKioqKioqVGVtcGxhdGUgU3RhcnRzIEhlcmUqKioqKioqKioqKi8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG5sIHB1dHMgKCIiKQojZGVmaW5lIHNwIHByaW50ZiAoICIgIiApCiNkZWZpbmUgcGhsIHByaW50ZiAoICJoZWxsb1xuIiApCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBQT1BDT1VOVCBfX2J1aWx0aW5fcG9wY291bnRsbAojZGVmaW5lIFJJR0hUTU9TVCBfX2J1aWx0aW5fY3R6bGwKI2RlZmluZSBMRUZUTU9TVCh4KSAoNjMtX19idWlsdGluX2NsemxsKCh4KSkpCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgRk9SKGkseCx5KSBmb3IodmxvbmcgaSA9ICh4KSA7IGkgPD0gKHkpIDsgKytpKQojZGVmaW5lIFJPRihpLHgseSkgZm9yKHZsb25nIGkgPSAoeSkgOyBpID49ICh4KSA7IC0taSkKI2RlZmluZSBDTFIoeCx5KSBtZW1zZXQoeCx5LHNpemVvZih4KSkKI2RlZmluZSBVTklRVUUoVikgKFYpLmVyYXNlKHVuaXF1ZSgoVikuYmVnaW4oKSwoVikuZW5kKCkpLChWKS5lbmQoKSkKI2RlZmluZSBNSU4oYSxiKSAoKGEpPChiKT8oYSk6KGIpKQojZGVmaW5lIE1BWChhLGIpICgoYSk+KGIpPyhhKTooYikpCiNkZWZpbmUgTlVNRElHSVQoeCx5KSAoKCh2bG9uZykobG9nMTAoKHgpKS9sb2cxMCgoeSkpKSkrMSkKI2RlZmluZSBTUSh4KSAoKHgpKih4KSkKI2RlZmluZSBBQlMoeCkgKCh4KTwwPy0oeCk6KHgpKQojZGVmaW5lIEZBQlMoeCkgKCh4KStlcHM8MD8tKHgpOih4KSkKI2RlZmluZSBBTEwoeCkgKHgpLmJlZ2luKCksKHgpLmVuZCgpCiNkZWZpbmUgTENNKHgseSkgKCgoeCkvZ2NkKCh4KSwoeSkpKSooeSkpCiNkZWZpbmUgU1ooeCkgKCh2bG9uZykoeCkuc2l6ZSgpKQojZGVmaW5lIE5PUk0oeCkgaWYoeD49bW9kKXgtPW1vZDsKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyB2bG9uZzsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdXZsb25nOwp0eXBlZGVmIHBhaXIgPCBpbnQsIGludCA+IHBpaTsKdHlwZWRlZiBwYWlyIDwgdmxvbmcsIHZsb25nID4gcGxsOwp0eXBlZGVmIHZlY3RvcjxwaWk+IHZpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKCmNvbnN0IHZsb25nIGluZiA9IDIxNDczODM2NDc7CmNvbnN0IGRvdWJsZSBwaSA9IDIgKiBhY29zICggMC4wICk7CmNvbnN0IGRvdWJsZSBlcHMgPSAxZS05OwoKCi8qKioqKioqKioqKlRlbXBsYXRlIEVuZHMgSGVyZSoqKioqKioqKioqLwpzdHJ1Y3QgewogICAgaW50IG47Cn1fZzsKcGxsIHBvaW50WzEwMTBdOwoKdmxvbmcgZ2V0QXJlYSAoIGludCBhLCBpbnQgYiwgaW50IGMgKSB7CiAgICBpZiAoIGIgPj0gX2cubiApIGIgLT0gX2cubjsKICAgIGlmICggYyA+PSBfZy5uICkgYyAtPSBfZy5uOwogICAgdmxvbmcgcmVzID0gcG9pbnRbYV0uZmYgKiBwb2ludFtiXS5zcyArIHBvaW50W2JdLmZmICogcG9pbnRbY10uc3MgKyBwb2ludFtjXS5mZiAqIHBvaW50W2FdLnNzOwogICAgcmVzIC09IHBvaW50W2FdLmZmICogcG9pbnRbY10uc3MgKyBwb2ludFtiXS5mZiAqIHBvaW50W2FdLnNzICsgcG9pbnRbY10uZmYgKiBwb2ludFtiXS5zczsKICAgIHJldHVybiBBQlMocmVzKTsKfQoKaW50IG14bGltaXRbMTAxMF1bMTAxMF07CgppbnQgYmluYXJ5U2VhcmNoICggaW50IGksIGludCBqLCBpbnQgbSAsIGludCBuLCB2bG9uZyBrICkgewoKICAgIC8vL0ZpcnN0IHNlYXJjaCBiZXR3ZWVuICAoaiArIDEpIC0gbQogICAgaW50IGxvdyA9IGogKyAxLCBoaWdoID0gbTsKCiAgICAvLy9VcHBlciBCb3VuZAogICAgd2hpbGUgKCBsb3cgPD0gaGlnaCApIHsKICAgICAgICBpbnQgbWlkID0gKCBsb3cgKyBoaWdoICkgLyAyOwoKICAgICAgICB2bG9uZyBhID0gZ2V0QXJlYSggaSwgaiwgbWlkICk7CgogICAgICAgIGlmICggYSA8PSBrICkgewogICAgICAgICAgICBsb3cgPSBtaWQgKyAxOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgaGlnaCA9IG1pZCAtIDE7CiAgICAgICAgfQogICAgfQoKICAgIGludCByZXMgPSAoIGxvdyAtIGogLSAxICk7CgogICAgLy8vTm93IHNlYXJjaCBiZXR3ZWVuIG0rMSAtIChuLTEpCiAgICBtID0gTUFYKG0rMSxqKzEpOwoKICAgIGlmICggbSA+PSBuICkgcmV0dXJuIHJlczsgLy8vTm8gbW9yZSBzZWdtZW50CgogICAgbG93ID0gbTsgaGlnaCA9IG4gLSAxOwoKICAgIC8vL0xvd2VyIEJvdW5kCiAgICB3aGlsZSAoIGxvdyA8PSBoaWdoICkgewogICAgICAgIGludCBtaWQgPSAoIGxvdyArIGhpZ2ggKSAvIDI7CgogICAgICAgIHZsb25nIGEgPSBnZXRBcmVhKCBpLCBqLCBtaWQgKTsKCiAgICAgICAgaWYgKCBhIDw9IGsgKSB7CiAgICAgICAgICAgIGhpZ2ggPSBtaWQgLSAxOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgbG93ID0gbWlkICsgMTsKICAgICAgICB9CiAgICB9CgogICAgcmVzICs9ICggbiAtIDEgKSAtIGxvdyArIDE7CgogICAgcmV0dXJuIHJlczsKfQoKaW50IG1haW4gKCkgewogICAgI2lmZGVmIGZvcnRocmlnaHQ0OAogICAgZnJlb3BlbiAoICJpbnB1dC50eHQiLCAiciIsIHN0ZGluICk7CiAgICAvL2ZyZW9wZW4gKCAib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0ICk7CiAgICAjZW5kaWYgLy8gZm9ydGhyaWdodDQ4CgogICAgaW50IGthc2U7CiAgICBzY2FuZiAoICIlZCIsICZrYXNlICk7CgogICAgd2hpbGUgKCBrYXNlLS0gKSB7CiAgICAgICAgaW50IG47CiAgICAgICAgdmxvbmcgbGltOwogICAgICAgIHNjYW5mICggIiVkICVsbGQiLCAmbiwgJmxpbSApOwogICAgICAgIGxpbSAqPSAyOwogICAgICAgIF9nLm4gPSBuOwoKICAgICAgICBGT1IoaSwwLG4tMSl7CiAgICAgICAgICAgIHNjYW5mICggIiVsbGQgJWxsZCIsICZwb2ludFtpXS5mZiwgJnBvaW50W2ldLnNzICk7CiAgICAgICAgfQoKICAgICAgICBpZiAoIG4gPD0gMiApIHsKICAgICAgICAgICAgcHJpbnRmICggIjBcbiIgKTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQoKCiAgICAgICAgLy8vRmluZCB0aGUgcG9pbnQgd2hpY2ggZ2l2ZXMgbWF4aW11bSBhcmVhIGZvciBnaXZlbiBwb2ludHMgKGksaikKICAgICAgICBGT1IoaSwwLG4tMSl7CiAgICAgICAgICAgIGludCBzID0gaSArIDE7IC8vL0luaXRpYXRlIHR3byBwb2ludGVyCiAgICAgICAgICAgIHZsb25nIHByZXYgPSAwOwogICAgICAgICAgICBGT1IoZixpKzEsbi0xKXsKICAgICAgICAgICAgICAgIHByZXYgPSBnZXRBcmVhKCBpLCBmLCBzICk7CiAgICAgICAgICAgICAgICAvLy9NYWtlIHMgZ28gZm9yd2FyZCBhcyBtdWNoIGFzIHBvc3NpYmxlCiAgICAgICAgICAgICAgICB3aGlsZSAoIDEgKSB7CiAgICAgICAgICAgICAgICAgICAgaWYgKCBzICsgMSA+PSBuICkgYnJlYWs7IC8vL05vdCBwb3NzaWJsZSB0byBnbyBmb3J3YXJkCiAgICAgICAgICAgICAgICAgICAgdmxvbmcgY3VyID0gZ2V0QXJlYSggaSwgZiwgcyArIDEgKTsKICAgICAgICAgICAgICAgICAgICBpZiAoIGN1ciA+PSBwcmV2ICkgewogICAgICAgICAgICAgICAgICAgICAgICBwcmV2ID0gY3VyOwogICAgICAgICAgICAgICAgICAgICAgICBzKys7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UgYnJlYWs7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgbXhsaW1pdFtpXVtmXSA9IHM7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHZsb25nIHJlcyA9IDA7CgogICAgICAgIC8vL0JpbmFyeSBTZWFyY2gKICAgICAgICBGT1IoaSwwLG4tMyl7CiAgICAgICAgICAgIEZPUihqLGkrMSxuLTIpewogICAgICAgICAgICAgICAgaW50IG0gPSBteGxpbWl0W2ldW2pdOwogICAgICAgICAgICAgICAgcmVzICs9IGJpbmFyeVNlYXJjaCAoIGksIGosIG0sIG4sIGxpbSApOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBwcmludGYgKCAiJWxsZFxuIiwgcmVzICk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K

Runtime error #stdin #stdout 0.01s 7460KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/JtJjt9

Blog 12426 - Counting Triangles

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language