Submission #31609

#	Time	Username	Problem	Language	Result	Execution time	Memory
31609		khsoo01	별자리 2 (JOI14_constellation2)	C++11	100 / 100	1993 ms	72684 KiB

constellation2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3005;

ll n, x[N], y[N], c[N], p[2*N], t[3], d[N][N], ans;

ll ccw (ll A, ll B, ll C) {
	return (x[A]*y[B]+x[B]*y[C]+x[C]*y[A])-(y[A]*x[B]+y[B]*x[C]+y[C]*x[A]);
}

bool isup (ll I) {
	return (x[I] >= x[p[1]] && y[I] >= y[p[1]]) || y[I] > y[p[1]];
}

bool cmp (ll A, ll B) {
	bool ba = isup(A), bb = isup(B);
	if(ba != bb) return ba;
	return ccw(p[1], A, B) > 0;
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld%lld",&x[i],&y[i],&c[i]);
	}
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=n;j++) {
			p[j] = j;
		}
		swap(p[1], p[i]);
		sort(p+2, p+1+n, cmp);
		for(ll j=2;j<=n;j++) {
			p[n+j-1] = p[j];
		}
		p[2*n] = p[2];
		ll E = 2; t[0] = t[1] = t[2] = 0;
		for(ll j=2;j<=n;j++) {
			t[c[p[j]]]--;
			while(ccw(i, p[j], p[E]) >= 0 && E < j+n-1) {
				t[c[p[E]]]++; E++;
			}
			d[i][p[j]] = 1;
			for(ll k=0;k<3;k++) {
				if(k != c[i]) d[i][p[j]] *= t[k];
			}
		}
	}
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=n;j++) {
			ans += d[i][j] * d[j][i];
		}
	}
	printf("%lld\n",ans/2);
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
constellation2.cpp:26:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&x[i],&y[i],&c[i]);
                                          ^

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45