Submission #105839

#	Time	Username	Problem	Language	Result	Execution time	Memory
105839		Pro_ktmr	Dragon 2 (JOI17_dragon2)	C++14	15 / 100	4086 ms	2472 KiB

dragon2

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

#define int long long
int N,M,Q;
vector<pair<int,int>> shu[30005];
int X1,Y1,X2,Y2;

bool cross(pair<int,int> from, pair<int,int> to){
	int ax = X1;
	int ay = Y1;
	int bx = X2;
	int by = Y2;
	int cx = from.first;
	int cy = from.second;
	int dx = to.first;
	int dy = to.second;

	//直線CAに対してBとDが同じ側にあるか
	//(ax-cx)*(Y-ay)-(ay-cy)*(X-ax)
	int tmp1 = (ax-cx)*(by-ay)-(ay-cy)*(bx-ax);
	int tmp2 = (ax-cx)*(dy-ay)-(ay-cy)*(dx-ax);
	if((tmp1 > 0) != (tmp2 > 0)) return false;
	//直線CBに対してAとDが同じ側にあるか
	//(bx-cx)*(Y-by)-(by-cy)*(X-bx)
	tmp1 = (bx-cx)*(ay-by)-(by-cy)*(ax-bx);
	tmp2 = (bx-cx)*(dy-by)-(by-cy)*(dx-bx);
	if((tmp1 > 0) != (tmp2 > 0)) return false;
	return true;
}

signed main(){
	cin >> N >> M;
	for(int i=0; i<N; i++){
		int A,B,C;
		cin >> A >> B >> C;
		shu[C].PB(MP(A,B));
	}
	cin >> X1 >> Y1 >> X2 >> Y2;

	//

	cin >> Q;
	for(int i=0; i<Q; i++){
		int A,B;
		cin >> A >> B;
		int ans = 0;
		for(int j=0; j<shu[A].size(); j++){
			for(int k=0; k<shu[B].size(); k++){
				//cout << shu[A][j].first << " " << shu[A][j].second << " " << shu[B][k].first << " " << shu[B][k].second << " " << cross(shu[A][j], shu[B][k]) << endl;
				if(cross(shu[A][j], shu[B][k])) ans++;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<shu[A].size(); j++){
                ~^~~~~~~~~~~~~~
dragon2.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0; k<shu[B].size(); k++){
                 ~^~~~~~~~~~~~~~

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