Submission #551896

#	Time	Username	Problem	Language	Result	Execution time	Memory
551896		LucaDantas	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4057 ms	1972 KiB

dragon2

#pragma GCC optimize("Ofast") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 30010;

struct Pt {
	int x, y;
	Pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
	long long operator/(const Pt& o) const { return 1ll * x * o.y - 1ll * y * o.x; }
	Pt operator-(const Pt& o) const { return Pt(x-o.x, y-o.y); }
};

bool cw(const Pt& a, const Pt& b, const Pt& c) { return (b-a)/(c-a) < 0; }
bool ccw(const Pt& a, const Pt& b, const Pt& c) { return (b-a)/(c-a) > 0; }

vector<Pt> tribe[maxn];

Pt v[2];

int main() {
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		int a, b, t; scanf("%d %d %d", &a, &b, &t);
		tribe[t].push_back(Pt(a, b));
	}
	for(int i = 0; i < 2; i++) {
		int a, b; scanf("%d %d", &a, &b);
		v[i] = Pt(a, b);
	}
	int q; scanf("%d", &q);
	while(q--) {
		int a, b; scanf("%d %d", &a, &b);
		int ans = 0;
		for(Pt p1 : tribe[a]) {
			if(ccw(p1, v[0], v[1]))
				swap(v[0], v[1]);
			for(Pt p2 : tribe[b])
				ans += cw(p1, v[0], p2) && ccw(p1, v[1], p2);
		}
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:27:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   int a, b, t; scanf("%d %d %d", &a, &b, &t);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   int a, b; scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
dragon2.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   int a, b; scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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