Submission #529049

#	Time	Username	Problem	Language	Result	Execution time	Memory
529049		penguinhacker	Kućice (COCI21_kucice)	C++14	110 / 110	76 ms	364 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct Point {
	ll x, y;
	Point operator-(const Point& o) const {
		return {x-o.x, y-o.y};
	}
	ll operator*(const Point& o) const {
		return x*o.y-y*o.x;
	}
};

const int mxN=1000, M=1e9+7;
int n, p2[mxN+1];
Point a[mxN], b[2*mxN];
ll ans;

void solve() {
	sort(b, b+n-1, [](Point x, Point y) {
		int tx=(x.y>0||x.x>0&&x.y==0)?1:2;
		int ty=(y.y>0||y.x>0&&y.y==0)?1:2;
		return tx!=ty?tx<ty:x*y>0;
	});
	for (int i=0; i<n-1; ++i)
		b[i+n-1]=b[i];
	ans=(ans+p2[n]-1)%M;
	for (int i=0, j=0; i<n-1; ++i) {
		j=max(j, i);
		while(j+1<i+n-1&&b[i]*b[j+1]>0)
			++j;
		ans=(ans-p2[j-i]+M)%M;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> a[i].x >> a[i].y;
	p2[0]=1;
	for (int i=1; i<=n; ++i)
		p2[i]=p2[i-1]*2%M;
	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j)
			if (i!=j)
				b[j-(j>i)]=a[j]-a[i];
		solve();
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:24:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |   int tx=(x.y>0||x.x>0&&x.y==0)?1:2;
      |                  ~~~~~^~~~~~~~
Main.cpp:25:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |   int ty=(y.y>0||y.x>0&&y.y==0)?1:2;
      |                  ~~~~~^~~~~~~~

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