oj.uz

Submission #776583

# Submission time Handle Problem Language Result Execution time Memory
776583 2023-07-08T04:31:27 Z myrcella Dragon 2 (JOI17_dragon2) C++17
15 / 100
 1616 ms 51260 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double DD;

#define int LL
#define pii pair<int,int>
#define F first
#define pq priority_queue
#define S second
#define inf 0x3f
#define pb push_back
#define SZ(x) ((int)((x).size()))
#define ALL(x) x.begin(), x.end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define MOD 1000000007
#define debug(x) cerr << #x << "=" << x << endl

const int maxn = 3333;

int n, _;
int ans[maxn][maxn];
pii coor[maxn];
int typ[maxn];
pii x, y;

DD calc(pii a, pii b, pii c) {
  /*
  DD tmp = (b.F - a.F) * (b.F - a.F) + (b.S - a.S) * (b.S - a.S);
  tmp += (c.F - a.F) * (c.F - a.F) + (c.S - a.S) * (c.S - a.S);
  tmp -= (b.F - c.F) * (b.F - c.F) + (b.S - c.S) * (b.S - c.S);
  tmp /= (DD(2) * sqrt((b.F - a.F) * (b.F - a.F) + (b.S - a.S) * (b.S - a.S)) * sqrt((c.F - a.F) * (c.F - a.F) + (c.S - a.S) * (c.S - a.S)));
  return tmp;
  */
  DD tmp = (b.F - a.F) * (c.F - a.F) + (b.S - a.S) * (c.S - a.S);
  debug(tmp);
  tmp /= sqrt((b.F - a.F) * (b.F - a.F) + (b.S - a.S) * (b.S - a.S));
  debug(tmp);
  tmp /= sqrt((c.F - a.F) * (c.F - a.F) + (c.S - a.S) * (c.S - a.S));
  return tmp;
}

signed main() {
  cin >> n >> _;
  rep(i, 0, n) {
	cin >> coor[i].F >> coor[i].S;
	cin >> typ[i];
  }
  cin >> x.F >> x.S >> y.F >> y.S;
  if (x.F > y.F) swap(x.F, y.F), swap(x.S, y.S);
  rep(i, 0, n)
    rep(j, 0, n) {
	  if (typ[i] == typ[j]) continue;
	  DD k1 = DD(coor[j].S - coor[i].S) / DD(coor[j].F - coor[i].F);
	  DD b1 = DD(coor[j].S) - DD(coor[j].F) * k1;
	  
	  DD k2 = DD(x.S - y.S) / DD(x.F - y.F);
	  DD b2 = DD(x.S) - DD(x.F) * k2;
	  
	  DD xx = DD(b2 - b1) / DD(k1 - k2);
	  if (xx < x.F or xx > y.F) continue;
	  if ((xx - coor[i].F) * DD(coor[i].F - coor[j].F) > 0) continue;
	  
	  //debug(i), debug(j);
      ans[typ[i]][typ[j]]++;
	}
  cin >> _;
  while (_--) {
	int a, b;
	cin >> a >> b;
	cout << ans[a][b] << "\n";
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 364 KB Output is correct
2 Correct 190 ms 420 KB Output is correct
3 Correct 210 ms 844 KB Output is correct
4 Correct 310 ms 11744 KB Output is correct
5 Correct 394 ms 51260 KB Output is correct
6 Correct 134 ms 2260 KB Output is correct
7 Correct 127 ms 2224 KB Output is correct
8 Correct 40 ms 340 KB Output is correct
9 Correct 42 ms 388 KB Output is correct
10 Correct 42 ms 384 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 1616 ms 46208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 364 KB Output is correct
2 Correct 190 ms 420 KB Output is correct
3 Correct 210 ms 844 KB Output is correct
4 Correct 310 ms 11744 KB Output is correct
5 Correct 394 ms 51260 KB Output is correct
6 Correct 134 ms 2260 KB Output is correct
7 Correct 127 ms 2224 KB Output is correct
8 Correct 40 ms 340 KB Output is correct
9 Correct 42 ms 388 KB Output is correct
10 Correct 42 ms 384 KB Output is correct
11 Runtime error 1616 ms 46208 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -