Submission #25760

#	Time	Username	Problem	Language	Result	Execution time	Memory
25760		zigui	별자리 2 (JOI14_constellation2)	C++14	100 / 100	1483 ms	1480 KiB

constellation2

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

pii operator-(const pii &l, const pii &r){
	return pii(l.first - r.first, l.second - r.second);
}

ll operator/(const pii &l, const pii &r){
	return (ll)l.first * r.second - (ll)l.second * r.first;
}

int sign(pii x){ return pii(0, 0) < x ? 1 : -1; }

const int MX = 3005;

struct star{
	star(){}
	star(pii p, int c):p(p), c(c){}
	pii p;
	int c;
}D[MX];
int N;

ll getm(int x[3], int y[3], int c1, int c2){
	ll m = 1;
	for(int i = 0; i < 3; i++){
		if( c1 != i ) m *= x[i];
		if( c2 != i ) m *= y[i];
	}
	return m;
}

ll solve(vector<star> &L, int c){
	int x[3] = {}, y[3] = {};
	sort(L.begin(), L.end(), [](star l, star r){
		return sign(l.p) != sign(r.p) ? sign(l.p) > sign(r.p) : l.p/r.p > 0;
	});
	int N = L.size();
	ll ans = 0;
	for(int i = 0; i < N; i++) L.push_back(L[i]);
	int r = 0;
	for(int i = 0; i < N; i++) y[L[i].c]++;
	for(int i = 0; i < N; i++){
		while(r < i+N && L[i].p/L[r].p >= 0 ){
			x[L[r].c]++; y[L[r].c]--;
			r++;
		}
		ans += getm(x, y, L[i].c, c);
		x[L[i].c]--; y[L[i].c]++;
	}
	return ans;
}

int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d%d%d", &D[i].p.first, &D[i].p.second, &D[i].c);
	ll ans = 0;
	for(int i = 1; i <= N; i++){
		vector<star> L;
		for(int j = 1; j <= N; j++){
			if( i != j ) L.emplace_back(D[j].p - D[i].p, D[j].c);
		}
		ans += solve(L, D[i].c);
	}
	printf("%lld\n", ans/2);
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:62:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
constellation2.cpp:63:85: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d%d%d", &D[i].p.first, &D[i].p.second, &D[i].c);
                                                                                     ^

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