Submission #157961

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
157961	2019-10-14 08:47:00	imyujin	Tri (CEOI09_tri)	C++17	100 / 100	465 ms	33200 KiB

tri

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
const int MAXN = 100010;
const int MX = 1 << 17;
int N, M;
pii dot[MAXN];
pii tri[MAXN][2], p[MAXN];
int qs[MAXN];
vector<int> que[2 * MX];
bool ans[MAXN];
vector<int> ch[2 * MX];
lint cp(pii a, pii b) { return (lint)a.fi * b.se - (lint)a.se * b.fi; }
lint ccw(pii a, pii b, pii c) { return cp(a, b) + cp(b, c) + cp(c, a); }
bool cmp(const pii a, const pii b) { return ccw(pii(0, 0), a, b) > 0; }
int lwb(pii &a) { return lower_bound(dot, dot + N, a, cmp) - dot; }
int upb(pii &a) { return upper_bound(dot, dot + N, a, cmp) - dot; }
pii operator-(pii a, pii b) { return pii(a.fi - b.fi, a.se - b.se); }
void addquery(int idx, int l, int r, int x, int y, int z) {
  if(x <= l && r <= y) que[idx].pb(z);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

tri.cpp: In function 'void f(int, int, int)':
tri.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ch[idx * 2].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
tri.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; t + 1 < ch[idx * 2 + 1].size(); t++)
          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:50:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i + 1 == ch[idx * 2].size() || ccw(dot[ch[idx * 2][i]], dot[ch[idx * 2][i + 1]], dot[ch[idx * 2 + 1][t]]) >= 0)
       ~~~~~~^~~~~~~~~~~~~~~~~~~~~
tri.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = t; i < ch[idx * 2 + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) >= ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
         ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100