QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#307281 | #7906. Almost Convex | icesmoke | WA | 0ms | 3616kb | C++14 | 2.0kb | 2024-01-18 12:32:40 | 2024-01-18 12:32:41 |
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) {
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];
signed main() {
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});
}
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;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 3616kb
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: 3588kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
6
result:
wrong answer 1st numbers differ - expected: '7', found: '6'