QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#613205 | #7906. Almost Convex | zhr05 | TL | 1ms | 4004kb | C++23 | 2.8kb | 2024-10-05 13:44:41 | 2024-10-05 13:44:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
int sgn(double x) {
if(fabs(x) < eps) return 0;
else return x<0?-1:1;
}
int Dcmp(double x, double y) {
if(fabs(x - y) < eps) return 0;
else return x<y ?-1:1;
}
struct Point {
double x,y;
Point(double x,double y):x(x),y(y) {}
Point() {}
Point operator + (Point B) {
return Point(x+B.x,y+B.y);
}
Point operator - (Point &B) {
return Point(x-B.x,y-B.y);
}
Point operator + (double rad) {
return Point(x*cos(rad)-y*sin(rad), x*sin(rad)+y*cos(rad)); //rotate
}
Point operator - (double rad) {
return (*this)+(-rad);
}
bool operator == (Point &B) {
return sgn(x-B.x)==0 && sgn(y-B.y)==0;
}
bool operator < (Point &B) {
return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0); //Convex Hull
}
double operator * (Point B) {
return x*B.x + y*B.y; //Dot
}
double operator ^ (Point B) {
return x*B.y - y*B.x; //Cross: >0 deg+ dir; <0 deg- dir ;=0 deg=0\180
}
double operator ~ () {
return hypot(x,y); //Len
}
};
typedef Point Vec;
// <vec A,vec B>
double Angle(Vec A,Vec B) {
return acos(A*B/(~A * ~B));
}
//Convex_hull()求凸包。凸包顶点放在ch中,返回值是凸包的顶点数
vector<Point> Convex_hull(vector<Point> &p) {
sort(p.begin(),p.end()); //对点排序:按x从小到大排序,如果x相同,按y排序
p.erase(unique(p.begin(),p.end()), p.end()); //remove simi
int v=0,n=p.size();
vector<Point> ch;
for(int i=0; i<n; i++) {
while(v>1 && sgn((ch[v-1]-ch[v-2])^(p[i]-ch[v-2]))<=0) ch.pop_back(),v--;
ch.emplace_back(p[i]),v++;
}//求下凸包。如果p[i]是右拐弯的,这个点不在凸包上,往回退
int j=v;
//求上凸包
for(int i=n-2; i>=0; i--) {
while(v>j && sgn((ch[v-1]-ch[v-2])^(p[i]-ch[v-2]))<=0) ch.pop_back(),v--;
ch.emplace_back(p[i]),v++;
}
if(n>1) ch.pop_back();
return ch; //convex_hull
}
long long Phash(Point A){
return (long long)A.x*10000000+A.y;
}
vector<Point>P,CH,NCH;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int N;
cin>>N;
for(int i=1,xx,yy; i<=N; i++) cin>>xx>>yy,P.emplace_back(xx,yy);
CH=Convex_hull(P);
unordered_map<long long,bool> MP;
for(auto i:CH) MP[Phash(i)]=1;
for(auto i:P) if(!MP[Phash(i)]) NCH.emplace_back(i);
int ans=1;
for(auto k:NCH) {
//vector<Point>Q;
//for(auto i:P) if(!(i==k)) Q.emplace_back(i);
auto cmp=[&](Point A,Point B)->bool{
if(A==k) return 1;
if(B==k) return 0;
return Angle(Point(1,0),A-k)<Angle(Point(1,0),B-k);
};
sort(P.begin(),P.end(),cmp);
for(int i=0,n=P.size(); i<n; i++)
if(MP[Phash(P[i])] && MP[Phash(P[(i+1)%n])]) ans++;
if(MP[Phash(P[1])] && MP[Phash(P[P.size()-1])]) ans++;
}
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3920kb
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: 3812kb
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: 3752kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4004kb
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: 3624kb
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...