QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310969 | #7906. Almost Convex | KiharaTouma | TL | 1ms | 4020kb | C++14 | 7.7kb | 2024-01-21 20:10:42 | 2024-01-21 20:10:42 |
Judging History
answer
//qoj7906
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std; typedef long long ll; namespace FastIO {
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc() { if (__builtin_expect(_read_ptr == _read_ptr_end, false)) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;} return *_read_ptr++; }
INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } }
INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; inline bool _isdigit(char c) { return (c & 16) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; }
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer; template <class T> INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed; template <class T> INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <> INLINE_V constexpr bool _is_integer<__int128> = true; template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true; template <> INLINE_V constexpr bool _is_signed<__int128> = true; template <> INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
inline void read(char &c) { do c = gc(); while (!_isgraph(c)); } inline void read_cstr(char *s) { char c = gc(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) s.push_back(c), c = gc(); }
template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void read(T &x) { char c = gc(); bool f = true; x = 0; while (!_isdigit(c)) { if (c == 45) f = false; c = gc(); }
if (f) while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); else while (_isdigit(c)) x = x * 10 - (c & 15), c = gc(); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void read(T &x) { char c = gc(); while (!_isdigit(c)) c = gc(); x = 0; while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); }
inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while (*s) pc(*s++); } inline void write(const string &s) { for (char c : s) pc(c); } template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; if (x >= 0) do buffer[digits++] = (x % 10) | 48, x /= 10; while (x);
else { pc(45); do buffer[digits++] = -(x % 10) | 48, x /= 10; while (x); } while (digits) pc(buffer[--digits]); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; do buffer[digits++] = (x % 10) | 48, x /= 10; while (x); while (digits) pc(buffer[--digits]); }
template <int N> struct _tuple_io_helper { template <class... T> static inline void _read(tuple<T...> &x) { _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x)); } };
template <> struct _tuple_io_helper<1> { template <class... T> static inline void _read(tuple<T...> &x) { read(get<0>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { write(get<0>(x)); } };
template <class... T> inline void read(tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_read(x); } template <class... T> inline void write(const tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_write(x); }
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); } template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first), pc(32), write(x.second); }
template <class T1, class... T2> inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template <class... T> inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template <class T1, class... T2> inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template <class... T> inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template <class T> inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template <class T1, class... T2> inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template <class... T> inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template <class... T> inline void println(const T &...x) { print(x...), pc(10); } template <class... T> inline void printk(const T &...x) { print(x...), pc(32); } template <class... T> inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; void solve();int main(){ solve(); return 0; }
const int N = 4e3 + 10;
const double eps = 1e-8;
int n, x[N], y[N], is[N], id[N];
int is0(double x){return (fabs(x)<eps?0:(x<0)?-1:1);}
struct Point{
double x,y;
int id;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator+(Point b){return Point(x+b.x,y+b.y);}
Point operator-(Point b){return Point(x-b.x,y-b.y);}
bool operator==(Point b){return is0(x-b.x)==0&&is0(y-b.y)==0;}
bool operator<(Point b){return is0(x-b.x)<0||(is0(x-b.x)==0&&is0(y-b.y)<0);}
}p[N],ch[N];
typedef Point Vector;
typedef Point point;
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double Dist(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
int Andrew(int n){
int v=0,k;
sort(p,p+n);
n=unique(p,p+n)-p;
for(int i=0; i<n; ++i){
while(v>1 && is0(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<1) --v;
ch[v++]=p[i];
}
for(int i=n-2,k=v; i>=0; --i){
while(v>k && is0(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<1) --v;
ch[v++]=p[i];
}
return (n>1?v-1:v);
}
bool cmp1(point x, point y){
if(atan2(x.y, x.x) != atan2(y.y, y.x)){
return atan2(x.y, x.x) < atan2(y.y, y.x);
}
return x.x < y.x;
}
int qdr(point x){
if(x.x > 0 && x.y >= 0) return 1;
if(x.x <= 0 && x.y > 0) return 2;
if(x.x < 0 && x.y <= 0) return 3;
if(x.x >= 0 && x.y < 0) return 4;
}
bool cmp(point x, point y){
if(qdr(x) == qdr(y)){
return cmp1(x, y);
} else {
return qdr(x) < qdr(y);
}
}
int v;
int calc(int k){
int cnt = 0, ans = 0;
for(int i = 0; i < n; ++ i){
if(i == k){
continue;
}
ch[++cnt].x = x[i] - x[k] + eps;
ch[cnt].y = y[i] - y[k] + eps;
ch[cnt].id = i;
}
sort(ch + 1, ch + cnt + 1, cmp);
ch[cnt+1] = ch[1];
for(int i = 1; i <= cnt; ++ i){
if(is[ch[i].id] && is[ch[i+1].id]){
if(abs(id[ch[i].id] - id[ch[i+1].id]) == 1){
++ ans;
} else if(id[ch[i].id] == v && id[ch[i+1].id] == 1){
++ ans;
} else if(id[ch[i].id] == 1 && id[ch[i+1].id] == v){
++ ans;
}
}
}
return ans;
}
void solve(){
read(n);
for(int i = 0; i < n; ++ i){
read(x[i], y[i]);
p[i].x = x[i];
p[i].y = y[i];
p[i].id = i;
}
v = Andrew(n);
for(int i = 0; i < v; ++ i){
is[ch[i].id] = 1;
id[ch[i].id] = i + 1;
}
int ans = 1;
for(int i = 0; i < n; ++ i){
if(!is[i]){
ans += calc(i);
}
}
println(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
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: 4012kb
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: 1ms
memory: 3704kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3940kb
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: 3536kb
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...