QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#608752 | #7906. Almost Convex | Doubeecat | TL | 0ms | 3960kb | C++20 | 2.8kb | 2024-10-04 02:28:03 | 2024-10-04 02:28:03 |
Judging History
answer
/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e3 + 10;
int dcmp(double a) {return a < -eps ? -1 : (a > eps ? 1 : 0);}
struct point {
double x,y;point(double X = 0,double Y = 0) {x = X,y = Y;}
friend point operator - (const point &a,const point &b) {
point c;
c.x = a.x - b.x;
c.y = a.y - b.y;
return c;
}
friend double operator ^ (const point &a,const point &b) {
return a.x * b.y - a.y * b.x;
}
}p[N],O;
bool cmp1(point a,point b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int convexhull(point *P,int n,int *cp) {
sort(P+1,P+n+1,cmp1);
int t = 0;
for (int i = 1;i <= n;++i) {
while (t > 1 && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
cp[++t] = i;
}
int st = t;
for (int i =n-1;i >= 1;--i) {
while (t > st && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
cp[++t] = i;
}
return --t;
}
int n,cp[N];
bool vis[N];
double theta(point a) {return atan2(a.y,a.x);}
bool lt(double a, double b) { return a - b < -eps; } // <
void psort(vector <int> &ps, point c) // 极角排序
{
sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
return lt(theta(p[p1] - c), theta(p[p2] - c));
});
}
signed main() {
read(n);
for (int i = 1;i <= n;++i) read(p[i].x,p[i].y);
int siz = convexhull(p,n,cp);
/*
for (int i = 1;i <= siz;++i) {
cout << p[cp[i]].x << " " << p[cp[i]].y << endl;
}
*/
for (int i = 1;i <= siz;++i) vis[cp[i]] = 1;
ll ans = 1;
for (int x = 1;x <= n;++x) {
if (vis[x]) continue;
vector <int> qwq;
for (int i = 1;i <= n;++i) {
if (i != x) qwq.push_back(i);
}
psort(qwq,p[x]);
int sz = qwq.size();
if (vis[qwq[0]] && vis[qwq[sz-1]])++ans;
for (int i = 1;i < sz;++i) {
if (vis[qwq[i]] && vis[qwq[i-1]])++ans;
}
}
cout <<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3960kb
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: 3952kb
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: 3608kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3952kb
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: 3488kb
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...