oj.uz

Submission #127902

# Submission time Handle Problem Language Result Execution time Memory
127902 2019-07-10T08:18:51 Z 이온조(#3109) Dragon 2 (JOI17_dragon2) C++14
15 / 100
 275 ms 35708 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define X first
#define Y second

struct dra {
	ll X, Y;
	int C;
};

int CCW(dra A, dra B, dra C) {
	ll tmp = A.X*B.Y + B.X*C.Y + C.X*A.Y - A.Y*B.X - B.Y*C.X - C.Y*A.X;
	if(tmp < 0LL) return -1;
	if(tmp == 0LL) return 0;
	if(tmp > 0LL) return +1;
}

int C[3009], ans[3009][3009];
dra A[3009], S, E;

bool intersect(dra A, dra B) {
	bool x = (CCW(S, E, A) != CCW(S, E, B));
	bool y = (CCW(A, B, S) != CCW(A, B, E));
	if(x && y) return true;
	if(!x && !y) return false;
	if(!x && CCW(S, E, A) != CCW(A, B, S)) return true;
	return false;
}

int main() {
	int N, M; scanf("%d%d",&N,&M);
	if(N > 3000) return 0;
	for(int i=1; i<=N; i++) scanf("%lld%lld%d", &A[i].X, &A[i].Y, &A[i].C);
	scanf("%lld%lld%lld%lld", &S.X, &S.Y, &E.X, &E.Y);
	
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++) {
			if(A[i].C == A[j].C) continue;
			ans[A[i].C][A[j].C] += intersect(A[i], A[j]);
		}
	}
	int Q; scanf("%d",&Q);
	while(Q--) {
		int u, v; scanf("%d%d",&u,&v);
		printf("%d\n", ans[u][v]);
	}
	return 0;
}

Compilation message

dragon2.cpp: In function 'int CCW(dra, dra, dra)':
dragon2.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:33:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M; scanf("%d%d",&N,&M);
            ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:35:31: 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("%lld%lld%d", &A[i].X, &A[i].Y, &A[i].C);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &S.X, &S.Y, &E.X, &E.Y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d",&Q);
         ~~~~~^~~~~~~~~
dragon2.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 376 KB Output is correct
2 Correct 193 ms 504 KB Output is correct
3 Correct 208 ms 888 KB Output is correct
4 Correct 248 ms 8056 KB Output is correct
5 Correct 275 ms 25972 KB Output is correct
6 Correct 171 ms 35708 KB Output is correct
7 Correct 179 ms 35680 KB Output is correct
8 Correct 107 ms 376 KB Output is correct
9 Correct 71 ms 376 KB Output is correct
10 Correct 70 ms 440 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 376 KB Output is correct
2 Correct 193 ms 504 KB Output is correct
3 Correct 208 ms 888 KB Output is correct
4 Correct 248 ms 8056 KB Output is correct
5 Correct 275 ms 25972 KB Output is correct
6 Correct 171 ms 35708 KB Output is correct
7 Correct 179 ms 35680 KB Output is correct
8 Correct 107 ms 376 KB Output is correct
9 Correct 71 ms 376 KB Output is correct
10 Correct 70 ms 440 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 Halted 0 ms 0 KB -