Submission #776583

#	Time	Username	Problem	Language	Result	Execution time	Memory
776583		myrcella	Dragon 2 (JOI17_dragon2)	C++17	15 / 100	1616 ms	51260 KiB

dragon2

#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 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40