Submission #25751

#	Time	Username	Problem	Language	Result	Execution time	Memory
25751		kriii	별자리 2 (JOI14_constellation2)	C++14	100 / 100	1433 ms	1512 KiB

constellation2

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int N,X[3030],Y[3030],C[3030];

struct pt{
	pt(){}
	pt(int x_, int y_, int c_){
		x = x_; y = y_; c = c_;
		d = atan2(y,x);
	}
	int x,y,c; double d;

	bool operator <(const pt &t)const{
		return d < t.d;
	}
}P[6060];

double pi = acos(-1.0);

int main()
{
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d %d %d",&X[i],&Y[i],&C[i]);

	long long ans = 0;
	for (int v=0;v<N;v++){
		int c = 0;
		for (int j=0;j<N;j++) if (j != v) P[c++] = pt(X[j]-X[v],Y[j]-Y[v],C[j]);
		sort(P,P+c);

		int A[3] = {0,};
		for (int i=0;i<c;i++){
			A[P[i].c]++;
			P[i+c] = P[i];
			P[i+c].d += 2 * pi;
		}

		int B[3] = {0,};
		for (int i=0,j=0;i<c;i++){
			while (P[i].d + pi > P[j].d) B[P[j++].c]++;
			long long res = 1;
			for (int k=0;k<3;k++) if (k != C[v]) res *= (A[k] - B[k]);
			B[P[i].c]--;
			for (int k=0;k<3;k++) if (k != P[i].c) res *= B[k];
			ans += res;
		}
	}
	printf ("%lld\n",ans/2);

	return 0;
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&N);
                 ^
constellation2.cpp:26:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<N;i++) scanf ("%d %d %d",&X[i],&Y[i],&C[i]);
                                                            ^

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