QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314187 | #7906. Almost Convex | haze | TL | 0ms | 4124kb | C++23 | 3.6kb | 2024-01-25 14:02:53 | 2024-01-25 14:02:53 |
Judging History
answer
/*
Author: Haze
2024/1/24
*/
#include <bits/stdc++.h>
#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;
inline ll read() {
ll s = 0;
bool fl = false;
char ch = (char) getchar();
while (!isdigit(ch)) {
if (ch == '-')fl = true;
ch = (char) getchar();
}
while (isdigit(ch)) {
s = s * 10 + (ch ^ 48);
ch = (char) getchar();
}
return fl ? -s : s;
}
#define LD long long
struct point{
LD x, y;
point(){}
point(LD _X,LD _Y) : x(_X), y(_Y){}
LD operator *(const point &A)const {
return x * A.x + y * A.y;
}
LD operator ^(const point &A)const{
return x * A.y - y * A.x;
}
point operator +(const point &A)const {
return point(x + A.x, y + A.y);
}
point operator -(const point &A)const {
return point(x - A.x, y - A.y);
}
double len(){
return sqrt(x * x + y * y);
}
bool operator ==(const point &A)const {
return A.x == x && A.y == y;
}
};
const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
const double eps = 1e-8;
int sgn(double X){
if(X > eps)return 1;
if(X < -eps)return -1;
return 0;
}
bool turn_left(point A, point B, point C){
return sgn((B - A) ^ (C - A)) < 0;
}
void convex_hull (vector<point> a, vector<point> &ret){
if(a.size() <= 2)return;
sort(a.begin(), a.end(), [](const point &A, const point &B){
return A.x == B.x ? A.y > B.y : A.x < B.x;
});
int n = a.size();
irep(i, 0, n - 1){
while(ret.size() > 1 &&
! turn_left(*(ret.end() - 2), *(ret.end() - 1), a[i]))
ret.pop_back();
ret.push_back(a[i]);
}
int fixed = (int)ret.size();
drep(i, n - 2, 0){
while(ret.size() > fixed &&
! turn_left(*(ret.end() - 2), *(ret.end() - 1), a[i]))
ret.pop_back();
ret.push_back(a[i]);
}
ret.pop_back();
return;
}
void solve() {
int n = read();
vector<point>a(n), con, ins;
vector<int>tp(n), ord(n);
//convex -> 1, inside -> 0
irep(i, 0, n - 1){
ll x = read(), y = read();
a[i] = point(x, y);
}
convex_hull(a, con);
int m = con.size();
ll ans = 1;
irep(i, 0, n - 1){
bool fl = 0;
irep(j, 0, m - 1){
if(a[i] == con[j]){
fl = 1;
break;
}
}
if(! fl)
ins.push_back(a[i]);
tp[i] = fl;
}
irep(i, 0, n - 1)ord[i] = i;
for(int i = 0; i < ins.size(); ++ i){
sort(ord.begin(), ord.end(), [&](int I, int J){
point A = a[I] - ins[i], B = a[J] - ins[i];
if(A == point(0, 0))return false;
if(B == point(0, 0))return true;
//UU < 0 0
return atan2(A.x, A.y) < atan2(B.x, B.y);
});
/*
cerr << "i = " << i << endl;
cerr << a[i].x << ' ' << a[i].y << '\n' << '\n';
irep(j, 0, n - 1){
cerr << a[ord[j]].x << ' ' << a[ord[j]].y << endl;
}
cerr << endl;
*/
for(int j = 0; j < n - 1; ++ j){
if(tp[ord[j]] == 1 && tp[ord[(j + 1) % (n - 1)]] == 1)
++ ans;
}
}
cout << ans;
}
int main() {
// IOS
int T = 1;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4020kb
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: 3944kb
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: 3600kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4124kb
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: 3728kb
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...