Submission #261776

#	Time	Username	Problem	Language	Result	Execution time	Memory
261776		onjo0127	별자리 (JOI12_constellation)	C++11	100 / 100	77 ms	5360 KiB

constellation

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(V) ((int)(V).size())
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;

struct star {
	int X, Y, ty;
} A[100009];

int CCW(star A, star B, star C) {
	ll tmp = 1LL*A.X*B.Y + 1LL*B.X*C.Y + 1LL*C.X*A.Y - 1LL*A.Y*B.X - 1LL*B.Y*C.X - 1LL*C.Y*A.X;
	if(tmp < 0) return -1;
	if(tmp == 0) return 0;
	if(tmp > 0) return +1;
}

long long get(int x) {
	long long ans = 1;
	for(int i=0; i<x; i++) ans *= 2, ans %= MOD;
	return ans;
}

int main() {
	int ct[3] = {0, 0, 0};
	int N; long long tot = 0;
	scanf("%d", &N);
	for(int i=1; i<=N; i++) {
		scanf("%d%d%d", &A[i].X, &A[i].Y, &A[i].ty);
		if(A[i].ty == 0) ++tot;
		++ct[A[i].ty];
	}
	sort(A+1, A+N+1, [&](star PP, star QQ) {
		if(PP.X == QQ.X) return PP.Y < QQ.Y;
		return PP.X < QQ.X;
	});
	vector<star> H;
	sort(A+2, A+N+1, [&](star PP, star QQ) { return CCW(A[1], PP, QQ) > 0; });
	H.push_back(A[1]); H.push_back(A[2]);
	for(int i=3; i<=N; i++) {
		while(sz(H) >= 2 && CCW(H[sz(H) - 2], H[sz(H) - 1], A[i]) < 0) H.pop_back();
		H.push_back(A[i]);
	}
	long long hto = 0;
	for(auto& it: H) if(it.ty == 0) ++hto;
	int p = -1, ch = 0, c = -1; long long cnt = 0, ans = 0;
	for(int i=0; i<H.size(); i++) if(H[i].ty) {
		p = i; c = H[i].ty;
		break;
	}
	int t = 0;
	if(!ct[1]) ++t;
	if(!ct[2]) ++t;
	if(p == -1) {
		ans = 1LL * hto * (hto - 1) + 2; ans %= MOD;
		ans *= get(tot - hto);
		printf("%lld", (ans + MOD - t) % MOD);
		return 0;
	}
	long long ans2 = 1;
	for(int i=p+1; i<=p+sz(H); i++) {
		int it = i % sz(H);
		if(H[it].ty) {
			if(H[it].ty == c) ans += 1LL * cnt * (cnt + 1) / 2, ans %= MOD;
			else ++ch, ans2 *= cnt + 1;
			c = H[it].ty;
			cnt = 0;
		}
		else ++cnt;
	}
	if(ch == 0) return !printf("%lld", ((ans + 1) * get(tot - hto) + MOD - t) % MOD);
	if(ch > 2) return !printf("0");
	ans2 %= MOD;
	printf("%lld", (ans2 * get(tot - hto) + MOD - t) % MOD);
	return 0;
}

Compilation message (stderr)

constellation.cpp: In function 'int main()':
constellation.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<H.size(); i++) if(H[i].ty) {
               ~^~~~~~~~~
constellation.cpp: In function 'int CCW(star, star, star)':
constellation.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
constellation.cpp: In function 'int main()':
constellation.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
constellation.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A[i].X, &A[i].Y, &A[i].ty);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10