Submission #714038

#	Time	Username	Problem	Language	Result	Execution time	Memory
714038		Username4132	Kućice (COCI21_kucice)	C++14	0 / 110	1 ms	340 KiB

Main

#pragma GCC optimize("trapv")
#include<iostream>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define F first
#define S second

const int MAXN=1010, MOD=1000000007;
int n;
pii pt[MAXN], arr[MAXN];

ll ex(ll b, int e){
    ll ret=1;
    while(e){
        if(e&1) ret = (ret*b)%MOD;
        b = (b*b)%MOD;
        e>>=1;
    }
    return ret;
}

bool up(pii a){
    return (a.S==0? (a.F>0) : (a.S>0));
}

ll signed_area(pii a, pii b, pii c){
    return (((ll)a.F)*b.S - ((ll)a.S)*b.F + ((ll)b.F)*c.S - ((ll)b.S)*c.F + ((ll)c.F)*a.S - ((ll)c.S)*a.F);
}

ll count(int ind){
    ll ret=0;
    copy(pt, pt+n, arr), swap(arr[ind], arr[n-1]);
    sort(arr, arr+n-1, [](pii a, pii b){
        pii A = {a.F - arr[n-1].F, a.S - arr[n-1].S};
        pii B = {b.F - arr[n-1].F, b.S - arr[n-1].S};
        return up(A)==up(B)? A.S*B.F < B.S*A.F : (up(A)>up(B));
    });
    forn(i, n-1){
        int cur=i, off=0;
        dforn(j, 10) if(off+(1<<j)<(n-1)){
            int nxt = (cur+(1<<j))%(n-1);
            if(signed_area(arr[n-1], arr[i], arr[nxt])>0){
                cur = nxt, off+=(1<<j);
            }
        }
        ret+=ex(2, off);
    }
    return ret+1;
}

int main(){
    ll ans=0;
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
    forn(i, n) ans+=count(i);
    printf("%d\n", ((int)(n*(ex(2, n)) - (ans%MOD) + MOD)%MOD));
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:58:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 30
• Subtask 5: 0 / 30