Submission #1240432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240432		emptypringlescan	Dragon 2 (JOI17_dragon2)	C++17	0 / 100	4091 ms	11808 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;
int n,m;
pair<pair<long long,long long>,int> arr[30005];
pair<__int128_t,__int128_t> seg[2];
long long ans[2005][2005];
bool inter(pair<__int128_t,__int128_t> a,pair<__int128_t,__int128_t> b){
	__int128_t a1=0;
	a1+=(seg[0].second+seg[1].second)*(seg[1].first-seg[0].first);
	a1+=(seg[1].second+a.second)*(a.first-seg[1].first);
	a1+=(a.second+seg[0].second)*(seg[0].first-a.first);
	__int128_t a2=0;
	a2+=(seg[0].second+seg[1].second)*(seg[1].first-seg[0].first);
	a2+=(seg[1].second+b.second)*(b.first-seg[1].first);
	a2+=(b.second+seg[0].second)*(seg[0].first-b.first);
	if((a1>0)==(a2>0)) return false;
	a1=0;
	a1+=(a.second+b.second)*(a.first-b.first);
	a1+=(seg[0].second+a.second)*(seg[0].first-a.first);
	a1+=(b.second+seg[0].second)*(b.first-seg[0].first);
	a2=0;
	a2+=(a.second+b.second)*(a.first-b.first);
	a2+=(seg[1].second+a.second)*(seg[1].first-a.first);
	a2+=(b.second+seg[1].second)*(b.first-seg[1].first);
	if((a1>0)==(a2>0)) return false;
	return true;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		cin >> arr[i].first.first >> arr[i].first.second >> arr[i].second;
	}
	long long x1,x2,x3,x4;
	cin >> x1 >> x2 >> x3 >> x4;
	seg[0]={x1,x2};
	seg[1]={x3,x4};
	for(int i=1; i<=n; i++){
		pair<long long,long long> ray[2];
		ray[0]=arr[i].first;
		for(int j=1; j<=n; j++){
			if(arr[i].second==arr[j].second) continue;
			pair<long long,long long> dir={arr[j].first.first-arr[i].first.first,arr[j].first.second-arr[i].first.second};
			ray[1].first=arr[i].first.first+dir.first*(long long)1e9;
			ray[1].second=arr[i].first.second+dir.second*(long long)1e9;
			//cout << i << ' ' << j << ' ' << ray[1].first << ' ' << ray[1].second << '\n';
			if(inter(ray[0],ray[1])){
				ans[arr[i].second][arr[j].second]++;
			}
		}
	}
	int q;
	cin >> q;
	while(q--){
		int a,b;
		cin >> a >> b;
		cout << ans[a][b] << '\n';
	}
}

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