Submission #234998

#	Time	Username	Problem	Language	Result	Execution time	Memory
234998		Pajaraja	별자리 2 (JOI14_constellation2)	C++17	100 / 100	1060 ms	692 KiB

constellation2

#include <bits/stdc++.h>
#define MAXN 3007
using namespace std;
struct point {
    long long x,y;
    int ind,c;
};
long long cnn[3],cnp[3];
int n;
point a[MAXN];
vector<pair<point,bool>> u;
long long orient(point p,point q,point r) 
{
    return (q.x-p.x)*(r.y-p.y)-(q.y-p.y)*(r.x-p.x);
}
bool operator <(point p,point q) 
{
    return orient(p,q,a[0])>0;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lld%lld%d",&a[i].x,&a[i].y,&a[i].c);
		a[i].ind=i;
	}
	long long res=0;
	for(int i=0;i<n;i++)
	{
		swap(a[i],a[0]);
		u.clear();
		for(int j=1;j<n;j++)
		{
			if(a[j].x>=a[0].x) u.push_back({a[j],true});
			else 
			{
				point f; f.x=2*a[0].x-a[j].x; f.y=2*a[0].y-a[j].y; f.ind=a[i].ind; f.c=a[j].c;
				u.push_back({f,false});
			}
		}
		sort(u.begin(),u.end());
		for(int j=0;j<3;j++) cnp[j]=cnn[j]=0;
		for(int j=0;j<u.size();j++)
		{
			if(u[j].second) cnp[u[j].first.c]++;
			else cnn[u[j].first.c]++;
		}
		for(int j=0;j<u.size();j++)
		{
			if(u[j].second) cnp[u[j].first.c]--;
			else cnn[u[j].first.c]--;
			long long t1=1,t2=1,t3=1,t4=1;
			for(int z=0;z<3;z++) if(a[0].c!=z) t1*=cnp[z];
			for(int z=0;z<3;z++) if(a[0].c!=z) t2*=cnn[z];
			for(int z=0;z<3;z++) if(u[j].first.c!=z) t3*=cnp[z];
			for(int z=0;z<3;z++) if(u[j].first.c!=z) t4*=cnn[z];
			res+=(t1*t4+t2*t3);
			if(!u[j].second) cnp[u[j].first.c]++;
			else cnn[u[j].first.c]++;
		}
	}
	//assert(res%4==0);
	res=res/4LL;
	printf("%lld",res);
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<u.size();j++)
               ~^~~~~~~~~
constellation2.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<u.size();j++)
               ~^~~~~~~~~
constellation2.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
constellation2.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d",&a[i].x,&a[i].y,&a[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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