QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307302 | #7906. Almost Convex | icesmoke | TL | 0ms | 4016kb | C++14 | 2.6kb | 2024-01-18 12:56:12 | 2024-01-18 12:56:13 |
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;
}
__int128 cross(int xi,int yi,int xj,int yj) { //计算叉积
return ((__int128)xi*yj-(__int128)xj*yi);
}
__int128 compare(point a,point b,point c) { //计算极角
return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
}
point 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;
// if(compare(c,a,b)==0) return a.x < b.x;
// return compare(c,a,b) < 0;
}
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];
pair<point,int>dr[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;
if(id1 != id2) g[id1][id2] = g[id2][id1] = 1;
// cout<<id1<<' ';
}
// cout<<'\n';
// cout<<'\n';
int ans = 1;
for(int i=0;i<n;i++){
if(st[i]) continue;
// vector<pair<point,int>>dr;
int idx = 0;
for(int j=0;j<n;j++){
if(i==j) continue;
dr[idx++] = {ar[j],j};
// dr.push_back({ar[j],j});
}
c = ar[i];
// cout<<c.x<<' '<<c.y<<'\n';
// sort(dr.begin(),dr.end(),cmp2);
sort(dr,dr+n-1,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];
// if(g[id1][id2]) cout<<id1<<' '<<id2<<'\n';
// cout<<id1<<' ';
}
// cout<<'\n';
}
cout<<ans;
}
// (0,0) (0,2) (0,1)
// (0,2) (3,2) (1,5)
// (0,0) (3,0) (1,4)
// (3,0) (3,2)
// (0,0) (3.0)
// (0,2) (3,2)
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3988kb
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: 4016kb
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: 3572kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3984kb
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: 3616kb
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...