QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665148 | #5604. Triangle Containment | enze114514 | WA | 140ms | 22152kb | C++20 | 10.0kb | 2024-10-22 06:34:39 | 2024-10-22 06:34:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
const ll INF = 1e18;
const int mod = (int)1e9 + 7;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
template<typename T>
struct Point{
T x, y;
ld eps;
Point() : x(0), y(0), eps(1e-9) {}
Point(T x, T y) : x(x), y(y), eps(1e-9) {}
void set_eps(T eps){
this->eps = eps;
}
Point operator+ (const Point& b){
return Point(x + b.x, y + b.y);
}
Point operator- (const Point& b){
return Point(x - b.x, y - b.y);
}
Point operator- (){
return Point(-x, -y);
}
Point operator* (T t) const{
return Point(x * t, y * t);
}
Point operator/ (T t) const{
return Point(x / t, y / t);
}
Point &operator+=(Point p) &{
x += p.x;
y += p.y;
return *this;
}
Point &operator-=(Point p) &{
x -= p.x;
y -= p.y;
return *this;
}
Point &operator*=(T v) &{
x *= v;
y *= v;
return *this;
}
Point &operator/=(T v) &{
x /= v;
y /= v;
return *this;
}
Point &operator=(const Point& b) &{
x = b.x;
y = b.y;
return *this;
}
friend Point operator+ (const Point& a, const Point& b){
return {a.x + b.x, a.y + b.y};
}
friend Point operator- (const Point& a, const Point& b){
return {a.x - b.x, a.y - b.y};
}
friend bool operator==(Point a, Point b){
return a.x == b.x && a.y == b.y;
}
int sign(T x){
if(fabs(x) < eps){
return 0;
}
if(x < 0){
return -1;
}
return 1;
}
bool cmp(T x, T y){
if(fabs(x - y) > eps){
return 0;
}
return 1;
}
bool cmp(const Point& a, const Point& b){
return cmp(a.x, b.x) && cmp(a.y, b.y);
}
T dot(const Point& a, const Point& b){
return a.x * b.x + a.y * b.y;
}
T square(Point a){
return dot(a, a);
}
T cross(const Point& a, const Point& b){
return a.x * b.y - a.y * b.x;
}
T cross(const Point& a, const Point& b, const Point& p){
return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
}
T get_len(const Point& a){
return sqrt(dot(a, a));
}
T get_angle(const Point& a, const Point& b){
return acos(dot(a, b) / get_len(a) / get_len(b));
}
T area(const Point& a, const Point& b, const Point& c){
return cross(b - a, c - a);
}
Point rotate(const Point& a, T angle){ //两个点就 b - a (b按a转)
T dx = a.x * cos(angle) + a.y * sin(angle);
T dy = -a.x * sin(angle) + a.y * cos(angle);
return Point(dx, dy);
}
Point intersect(const Point& p, const Point& v, const Point& q, const Point& w){
Point u = p - q;
T t = cross(w, u) / cross(v, w);
return p + v * t;
}
T point_dist(const Point& a, const Point& b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
T line_dist(const Point& a, const Point& b, const Point& p){
Point u = b - a, v = p - a;
return fabs(cross(u, v)) / get_len(u);
}
T get_slope(const Point& a, const Point& b){
if(b.y == a.y) return INF;
if(b.x == a.x) return 0;
return (b.y - a.y) / (b.x - a.x);
}
T circle_intersect(const Point& p1, const Point& p2, const T r1, const T r2){
ld d = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
if(d > r1 + r2 || d + chmin(r1, r2) <= chmax(r1, r2)){
return 0;
}
else if(d == r1 + r2){
return 1;
}
else{
return 2;
}
}
T seg_dist(const Point& a, const Point& b, const Point& p){
if(a == b){
return get_len(p - a);
}
Point u = b - a, v = p - a, w = p - b;
if(sign(dot(u, v)) < 0){
return get_len(v);
}
if(sign(dot(u, w)) > 0){
return get_len(w);
}
return line_dist(a, b, p);
}
Point projection(const Point& a, const Point& b, const Point& p){
Point v = b - a;
return a + v * dot(v, p - a) / get_len(v);
}
bool on_segment(const Point& a, const Point& b, const Point& p){
bool u = sign(cross(p - a, p - b)) == 0;
bool v = sign(dot(p - a, p - b)) <= 0;
return u && v;
}
bool seg_intersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2){
T c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
T c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
}
friend std::ostream &operator<<(ostream &os, Point p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
const int deg = 180;
bool cmp(vector<ld> a, vector<ld> b){
return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
}
template<class Operation, class Mark>
struct SegTree{
const int n;
vector<Operation> op;
vector<Mark> mrk;
SegTree(int n) : n(n), op(4 << __lg(n)), mrk(4 << __lg(n)){
function<void(int, int, int)> build = [&](int u, int l, int r){
op[u] = Operation();
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
};
build(1, 1, n);
}
void pushup(int u){
op[u] = op[u << 1] + op[u << 1 | 1];
}
void modify(int u, const Mark &mk){
op[u].modify(mk);
mrk[u].modify(mk);
}
void pushdown(int u) {
modify(u << 1, mrk[u]);
modify(u << 1 | 1, mrk[u]);
mrk[u] = Mark();
}
void update(int u, int l, int r, int x, const Operation &v){
if(l == r){
op[u] = v;
return;
}
int m = (l + r) >> 1;
pushdown(u);
if(x <= m){
update(u << 1, l, m, x, v);
}
else{
update(u << 1 | 1, m + 1, r, x, v);
}
pushup(u);
}
void update(int u, const Operation &v){
update(1, 1, n, u, v);
}
Operation query(int u, int l, int r, int x, int y){
if(x <= l && r <= y) {
return op[u];
}
int m = (l + r) >> 1;
Operation cur;
pushdown(u);
if(x <= m){
cur = query(u << 1, l, m, x, y);
}
if(y > m){
cur = cur + query(u << 1 | 1, m + 1, r, x, y);
}
return cur;
}
Operation query(int l, int r){
return query(1, 1, n, l, r);
}
void range_update(int u, int l, int r, int x, int y, const Mark &v){
if(l >= x && r <= y){
modify(u, v);
return;
}
int m = (l + r) >> 1;
pushdown(u);
if(x <= m){
range_update(u << 1, l, m, x, y, v);
}
if(y > m){
range_update(u << 1 | 1, m + 1, r, x, y, v);
}
pushup(u);
}
void range_update(int l, int r, const Mark &v){
return range_update(1, 1, n, l, r, v);
}
};
struct Mark{
void modify(const Mark &v){
}
};
struct Operation {
ll sum = 0;
Operation(ll p = 0){
sum = p;
}
void modify(const Mark &v){
}
};
Operation operator+(Operation a, Operation b){
return {a.sum + b.sum};
}
void solve() {
int n;
ld ox;
cin >> n >> ox;
Point<ld> p1 = {0, 0}, p2 = {ox, 0};
vector<ld> all_angles;
vector<vector<ld>> a;
a.push_back({0}); // Placeholder to make indexing 1-based
for(int i = 0; i < n; i++) {
ld x, y, z;
cin >> x >> y >> z;
Point<ld> p = {x, y};
// Compute angles
ld dl = p.get_angle(p - p1, p2 - p1);
ld dr = p.get_angle(p - p2, p1 - p2);
// Store angles
all_angles.push_back(dl);
all_angles.push_back(dr);
// Store data
a.push_back({dl, dr, x, y, z, (ld)(i + 1)});
}
// Coordinate Compression
sort(all_angles.begin(), all_angles.end());
all_angles.erase(unique(all_angles.begin(), all_angles.end()), all_angles.end());
// Map angles to indices
map<ld, int> angle_to_index;
for(int i = 0; i < all_angles.size(); i++) {
angle_to_index[all_angles[i]] = i + 1; // 1-based index
}
// Update a and b with integer indices
vector<int> b;
for(int i = 1; i <= n; i++) {
a[i][0] = angle_to_index[a[i][0]]; // dl index
a[i][1] = angle_to_index[a[i][1]]; // dr index
b.push_back((int)a[i][1]); // dr indices
}
// Now, proceed with integer indices
sort(a.begin() + 1, a.end(), cmp);
sort(b.begin(), b.end());
map<int, int> mp;
// Build the segment tree
SegTree<Operation, Mark> tr(all_angles.size() + 1); // Size based on compressed angles
vector<ll> p(n + 1);
for(int i = 0; i < b.size(); i++) {
mp[b[i]] = i + 1;
}
for(int i = n; i >= 1; i--) {
int idx = (int)a[i][5];
int angle_idx = mp[(int)a[i][1]];
p[idx] = tr.query(1, angle_idx).sum;
tr.update(angle_idx, (ll)a[i][4]);
}
for(int i = 1; i <= n; i++) {
cout << p[i] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
input:
5 8 -8 1 1 -1 10 2 0 3 4 7 1 8 8 2 16
output:
0 12 0 0 8
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
6 6 0 1 1 2 3 10 2 5 100 3 1 1000 3 5 10000 4 5 100000
output:
0 1000 1010 0 1010 1000
result:
ok 6 lines
Test #3:
score: -100
Wrong Answer
time: 140ms
memory: 22152kb
input:
99999 1000000000 500002962 1 1 500025469 1 1 500044229 1 1 500026049 1 1 499983663 1 1 499965983 1 1 499988191 1 1 499987116 1 1 500029240 1 1 499975570 1 1 499973295 1 1 499986404 1 1 500023312 1 1 499964976 1 1 499952153 1 1 500046927 1 1 499951857 1 1 499984523 1 1 500038724 1 1 499991318 1 1 500...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer 1st lines differ - expected: '0', found: '1'