QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307413 | #7906. Almost Convex | icesmoke | TL | 1ms | 4032kb | C++14 | 2.2kb | 2024-01-18 15:43:20 | 2024-01-18 15:43:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sc second
struct point {
int x,y;
};
bool cmp(point p1,point p2) {
if(p1.x!=p2.x) return p1.x<p2.x;
return p1.y<p2.y;
}
int cross(int xi,int yi,int xj,int yj) { //计算叉积
return (xi*yj-xj*yi);
}
point c;
// c为当前选择的极点
// 求极角判断极角大小
bool cmp1(point a,point b) {
double o1 = atan2(a.y-c.y,a.x-c.x);
double o2 = atan2(b.y-c.y,b.x-c.x);
return o1 < o2;
}
bool cmp2(pair<point,int>p1,pair<point,int>p2){
return cmp1(p1.fs,p2.fs);
}
int check(point a1,point a2,point b)
{
int x1 = a2.x-a1.x,y1 = a2.y-a1.y;
int x2 = b.x-a1.x,y2 = b.y-a1.y;
return cross(x1,y1,x2,y2)>0;
}
int g[2005][2005];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
vector<point>ar(n);
for(int i=0; i<n; i++) {
cin>>ar[i].x>>ar[i].y;
}
sort(ar.begin(),ar.end(),cmp);
//求凸包
int m = 0;
vector<int>st(n);
vector<pair<point,int>>br;
for(int i=0;i<n;i++){
while(br.size()>=2 && check(br[br.size()-2].fs,br[br.size()-1].fs,ar[i])){
pair<point,int> t = br.back();
st[t.sc] = 0;
br.pop_back();
}
st[i] = 1;
br.push_back({ar[i],i});
}
m = br.size();
st[0] = 0;
for(int i=n-1;i>=0;i--){
if(st[i]) continue;
while(br.size()>=2 && check(br[br.size()-2].fs,br[br.size()-1].fs,ar[i])){
pair<point,int> t = br.back();
st[t.sc] = 0;
br.pop_back();
}
st[i] = 1;
br.push_back({ar[i],i});
}
if(br.back().sc==br[0].sc) br.pop_back();
m = br.size();
for(int i=0;i<m;i++){
int id1 = br[i].sc,id2 = br[(i+1)%m].sc;
g[id1][id2] = g[id2][id1] = 1;
// 标记(id1,id2),(id2,id1)为凸包上的相邻点对
}
int ans = 1;
for(int i=0;i<n;i++){
if(st[i]) continue;
// 选择不在凸包上的一个点作为极点,对其余点进行极点排序
vector<pair<point,int>>dr;
for(int j=0;j<n;j++){
if(i==j) continue;
dr.push_back({ar[j],j});
}
c = ar[i];
sort(dr.begin(),dr.end(),cmp2);
for(int j=0;j<n-1;j++){
int id1 = dr[j].sc,id2 = dr[(j+1)%(n-1)].sc;
ans += g[id1][id2];
}
}
cout<<ans;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4032kb
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: 1ms
memory: 3824kb
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: 3552kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3904kb
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: 3740kb
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...