QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#613008 | #7906. Almost Convex | zhr05 | TL | 1ms | 4112kb | C++23 | 4.1kb | 2024-10-05 13:25:19 | 2024-10-05 13:25:26 |
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));
}
//Area
double Area(Point A, Point B, Point C) {
return ((B-A)^(C-A)) /2.00;
}
struct Line {
Point p1,p2;//2Points
Line(Point p1,Point p2):p1(p1),p2(p2) {}
};
bool on_Seg(Point p, Line v) {
return sgn((p-v.p1)^(v.p2-v.p1)) == 0 && sgn((p - v.p1)*(p- v.p2)) <= 0;
}
//判断点和任意多边形的关系: 3 点上; 2 边上; 1 内部; 0 外部
//点pt,多边形的点Point *p,多边形点的数量n,多边形顶点按照顺时针或者逆时针方向排列
int Point_in_polygon(vector<Point> &p,Point &pt) {
int n=p.size();
for(int i = 0; i < n; i++) if(p[i] == pt) return 3;// On_Point
for(int i = 0; i < n; i++) if(on_Seg(pt,Line(p[i],p[(i+1)%n]))) return 2;// On_Edge
int num = 0;
for(int i = 0; i < n; i++) {
int j = (i+1)% n;
int c = sgn((pt-p[j])^(p[i]-p[j]));
int u = sgn(p[i].y - pt.y);
int v = sgn(p[j].y - pt.y);
if(c > 0 && u < 0 && v >=0) num++;
if(c < 0 && u >=0 && v < 0) num--;
}
return num != 0; //1-inside; 0-outside
}
double Polygon_area(vector<Point> &p) {
double area = 0;
for(int i=0,n=p.size(); i<n; i++)
area+=p[i]^p[(i+1)%n];
return area/2;//面积有正负,不能简单地取绝对值
}
//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
}
vector<Point>P,CH,NCH;
bool check(Vec A,Vec B,Vec C) {
vector<Point>V= {A,B,C};
for(auto i:NCH) {
if(i==C) continue;
if(Point_in_polygon(V,i)) return 0;
}
return 1;
}
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);
map<Point,bool,
decltype([](auto& p1,auto& p2) {
return p1.x==p2.x ? p1.y<p2.y:p1.x<p2.x;
})> MP;
for(auto i:CH) MP[i]=1;
for(auto i:P) if(!MP[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[P[i]] && MP[P[(i+1)%n]]) ans++;
if(MP[P[1]] && MP[P[P.size()-1]]) ans++;
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4112kb
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: 4008kb
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: 3480kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4072kb
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: 3484kb
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...