Submission #1196979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196979		sleepntsheep	별자리 2 (JOI14_constellation2)	C++20	100 / 100	829 ms	480 KiB

constellation2

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>

#define N 3000

int n, X[N], Y[N], x[N], y[N], c[N], ii[N], f1[3], f2[3], side[N];
long long answer;

int up(int i) {
    return y[i] > 0 || (! y[i] && x[i] >= 0);
}

int quad(int x, int y) {
    return ((x>=0)^(y>=0))|((y>=0)<<1);
}

int compar(int i, int j) {

    if ((long long)x[i] * y[j] == (long long)x[j] * y[i])
	return x[i] < x[j];

    //if (quad(x[i], y[i]) != quad(x[j], y[j])) return quad(x[i], y[i]) - quad(x[j], y[j]);

    long long x_ = (long long)x[i] * y[j] - (long long)x[j] * y[i];
    return (x_ > 0) ^ (x[i] < 0) ^ (x[j] < 0);
}

/* two triangle are seperate if there exists a line seperating them
* n ^ 3 sol - try each pair of point which determine a tangent line between two triangle
* then count colors on upper/lower half of the plane
*
* n ^ 2 lg n sol - fix first point, radial sweep on second point
* */

long long cross(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - y1 * x2;
}

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

    for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j) {
	    x[j] = X[j] - X[i];
	    y[j] = Y[j] - Y[i];
	}

	for (int j_ = 0, j = 0; j < n; ++j) {
	    if (j == i)
		continue;
	    ii[j_++] = j;
	}

	std::sort(ii, ii + n - 1, compar);

	f1[0] = f1[1] = f1[2] = 0;
	f2[0] = f2[1] = f2[2] = 0;

	for (int j = 0; j < n; ++j) {
	    if (j == i)
		continue;
	    //side[j] = cross(x[ii[0]] - x[i], y[ii[0]] - y[i], x[j] - x[ii[0]], y[j] - y[ii[0]]) >= 0 ? 1 : 0;//y[j] >= 0 ? 1 : 0;
	    side[j] = x[j] >= 0 ? 1 : 0;
	    if (side[j])
		++f1[c[j]];
	    else
		++f2[c[j]];
	}

	for (int o, i_ = 0; i_ + 1 < n; ++i_) {
	    o = ii[i_];
	    if (side[o]) --f1[c[o]];
	    else --f2[c[o]];

	    long long x_;

	    x_ = 1;
	    for (int q = 0; q < 3; ++q) if (q != c[i]) x_ *= f1[q];
	    for (int q = 0; q < 3; ++q) if (q != c[o]) x_ *= f2[q];
	    answer += x_;

	    x_ = 1;
	    for (int q = 0; q < 3; ++q) if (q != c[i]) x_ *= f2[q];
	    for (int q = 0; q < 3; ++q) if (q != c[o]) x_ *= f1[q];
	    answer += x_;

	    side[o] ^= 1;
	    if (side[o]) ++f1[c[o]];
	    else ++f2[c[o]];
	}
    }

    printf("%lld\n", answer / 4);

    return 0;
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
constellation2.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d%d%d", &X[i], &Y[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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