oj.uz

Submission #105839

# Submission time Handle Problem Language Result Execution time Memory
105839 2019-04-15T10:30:24 Z Pro_ktmr Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 2472 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1152 KB Output is correct
2 Correct 58 ms 1144 KB Output is correct
3 Correct 59 ms 1400 KB Output is correct
4 Correct 253 ms 2472 KB Output is correct
5 Correct 259 ms 2296 KB Output is correct
6 Correct 15 ms 1152 KB Output is correct
7 Correct 10 ms 1152 KB Output is correct
8 Correct 21 ms 1280 KB Output is correct
9 Correct 25 ms 1152 KB Output is correct
10 Correct 22 ms 1152 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2355 ms 2456 KB Output is correct
2 Execution timed out 4086 ms 2412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1152 KB Output is correct
2 Correct 58 ms 1144 KB Output is correct
3 Correct 59 ms 1400 KB Output is correct
4 Correct 253 ms 2472 KB Output is correct
5 Correct 259 ms 2296 KB Output is correct
6 Correct 15 ms 1152 KB Output is correct
7 Correct 10 ms 1152 KB Output is correct
8 Correct 21 ms 1280 KB Output is correct
9 Correct 25 ms 1152 KB Output is correct
10 Correct 22 ms 1152 KB Output is correct
11 Correct 2355 ms 2456 KB Output is correct
12 Execution timed out 4086 ms 2412 KB Time limit exceeded
13 Halted 0 ms 0 KB -