Submission #1240393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240393		salmon	Dragon 2 (JOI17_dragon2)	C++20	15 / 100	4091 ms	37660 KiB

dragon2

#include <bits/stdc++.h>
#include <numbers>
using namespace std;

int N;
int M;
int Q;
int T[30100];
vector<int> bel[30100];
int precomp[3100][3100];
const long double PI = 3.141592654;

struct vec{
	long double x;
	long double y;
	
} drag[30100], t1,t2;


//negative means clockwise, positive means anti
long double area(vec v1, vec v2, vec v3){
	return (v1.x - v2.x) * (v1.y + v2.y) + (v2.x - v3.x) * (v2.y + v3.y) + (v3.x - v1.x) * (v3.y + v1.y);
}
long double angle(vec v1, vec v2){
	return atan2(v2.y-v1.y,v2.x - v1.x);
}


int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	
	for(int i = 0; i < N; i++){
		int x,y;
		scanf(" %d %d",&x,&y);
		drag[i] = {(long double)x,(long double)y};
	
		int c;
		scanf(" %d",&c);
		bel[c].push_back(i);
		T[i] = c;
	}
	
	int x, y;
	scanf(" %d",&x);
	scanf(" %d",&y);
	
	t1 = {(long double)x,(long double)y};
	
	scanf(" %d",&x);
	scanf(" %d",&y);
	
	t2 = {(long double)x,(long double)y};

	for(int i = 1; i <= M; i++){
		for(int j = 1; j <= M; j++){
			if(i == j) continue;
			
			precomp[i][j] = 0;
			
			for(int di : bel[i]){
				for(int dj : bel[j]){
					precomp[i][j]++;
					
					if(area(drag[di], t1,t2) > 0){
						long double a = angle(t1,drag[di]);
						long double b = angle(t1,drag[dj]);
						
						if(a <= 0){
							if(a < b && b < a + PI){
								precomp[i][j]--;
								continue;
							}
						}
						else{
							if(b < a - PI || a < b){
								precomp[i][j]--;
								continue;
							}
						}
						
						a = angle(t2,drag[di]);
						b = angle(t2,drag[dj]);
						
						if(a <= 0){
							if(b < a || a + PI < b){
								precomp[i][j]--;
							}
						}
						else{
							if(a - PI < b && b < a){
								precomp[i][j]--;
							}
						}
					}
					else{
						long double a = angle(t2,drag[di]);
						long double b = angle(t2,drag[dj]);
						
						if(a <= 0){
							if(a < b && b < a + PI){
								precomp[i][j]--;
								continue;
							}
						}
						else{
							if(b < a - PI || a < b){
								precomp[i][j]--;
								continue;
							}
						}
						
						a = angle(t1,drag[di]);
						b = angle(t1,drag[dj]);
						
						if(a <= 0){
							if(b < a || a + PI < b){
								precomp[i][j]--;
							}
						}
						else{
							if(a - PI < b && b < a){
								precomp[i][j]--;
							}
						}
					}
					
					//printf("%d %d %d\n",precomp[i][j],di,dj);
					
				}
			}
		}
	}
	
	scanf(" %d",&Q);
	
	for(int i = 0; i < Q; i++){
		int a;
		int b;
		
		scanf(" %d",&a);
		scanf(" %d",&b);
		
		printf("%d\n",precomp[a][b]);
	}
	
	
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |                 scanf(" %d %d",&x,&y);
      |                 ~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                 scanf(" %d",&c);
      |                 ~~~~~^~~~~~~~~~
dragon2.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf(" %d",&x);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf(" %d",&y);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf(" %d",&x);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf(" %d",&y);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:142:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |                 scanf(" %d",&a);
      |                 ~~~~~^~~~~~~~~~
dragon2.cpp:143:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |                 scanf(" %d",&b);
      |                 ~~~~~^~~~~~~~~~

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