QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313616 | #7906. Almost Convex | xiaoxing666 | TL | 1ms | 3584kb | C++17 | 3.2kb | 2024-01-24 21:17:26 | 2024-01-24 21:17:26 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long db;
const db EPS = 0;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; } //点乘
db det(P p) { return x * p.y - y * p.x; } //叉乘
db distTo(P p) { return (*this-p).abs(); }
db alpha() { return atan2(y, x); }
void read() { cin>>x>>y; }
void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
db abs() { return sqrt(abs2());}
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);} //旋转90度
P unit() { return *this/abs(); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
P rot(db an){ return {x*cos(an) - y*sin(an),x*sin(an) + y*cos(an)}; } //旋转任意度
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3)) //逆时针正,顺时针负,共线0
vector<P> convexHull(vector<P> ps) { //严格凸包
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
int n;
vector<P> p;
map<P, int> mp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
{
db x, y;
cin >> x >> y;
p.push_back({x, y});
}
int ans = 0;
vector<P> q = convexHull(p);
for(auto tmp : q)
{
mp[tmp] = 1;
}
vector<P> nw;
for(int i = 0; i < n; i++)
{
if(mp[p[i]] == 0)
{
nw.push_back(p[i]);
}
}
vector<P> con;
int sz = q.size();
for(auto now : nw)
{
con.clear();
for(auto tmp : p)
{
if(tmp == now)
{
continue;
}
else{
con.push_back(tmp - now);
}
}
for(int i = 0; i < sz; i++)
{
int consz = con.size();
P pre = q[i] - now, nxt = q[(i + 1) % sz] - now;
sort(con.begin(), con.end(), [&](P a, P b) {
int qa = a.quad(), qb = b.quad();
if (qa != qb) return qa < qb;
else return sign(a.det(b)) > 0;
});
int l = 0, r = con.size() - 1;
while(l < r)
{
int mid = (l + r) / 2;
if(pre.quad() == con[mid].quad())
{
if(sign(con[mid].det(pre)) > 0)
l = mid + 1;
else r = mid;
}
else{
if(pre.quad() > con[mid].quad())
l = mid + 1;
else
r = mid;
}
}
if(con[(l + 1) % consz] == nxt || con[(l - 1 + consz) % consz] == nxt)
ans++;
}
}
cout << ans + 1 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3556kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...