QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276890 | #7906. Almost Convex | Redcrown# | WA | 1ms | 3736kb | C++17 | 3.6kb | 2023-12-06 12:21:13 | 2023-12-06 12:21:13 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=4e3+5;
int n,m;
inline int red(){
int data=0;bool w=0;char ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
if(ch=='-') w=1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return w?-data:data;
}
struct point{
ll x,y;
bool tp;
point(){}
point(ll a,ll b):x(a),y(b){}
void in(){
scanf("%lld%lld",&x,&y);
}
void out(){
printf("x:%lld y:%lld\n",x,y);
}
point operator -(const point &a)const{
return point(x-a.x,y-a.y);
}
ll operator ^(const point &a)const{
return x*a.y-y*a.x;
}
ll operator *(const point &a)const{
return x*a.x+y*a.y;
}
bool operator <(const point &a)const{
return x<a.x||(x==a.x&&y<a.y);
}
int toleft(const point &a)const{
const ll t=(*this)^a;
return (t>0)-(t<0);
}
bool operator ==(const point &a)const{
return x==a.x&&y==a.y;
}
};
ll judge,cvxs[N],cvxindx[N];
vector <point> points,ans;
bool cmp(ll x,ll y){
return points[x]<points[y];
}
ll convexhall(vector <point> &points, ll n, vector <point> &ans){
ll i,sz=0,k,a,x,no,flag=0,ok=1;
for(i=1;i<=n;i++) cvxindx[i]=i;
sort(cvxindx+1,cvxindx+n+1,cmp);
for(i=1;i<=n;i++){
a=cvxindx[i];
no=0;
while(sz>1){
x=(points[cvxs[sz-2]]-points[cvxs[sz-1]]).toleft(points[a]-points[cvxs[sz-1]]);
if(x==0) no=1;
if(x>=0){
sz--;
if(sz<flag)flag=0;
}else{
break;
}
}
if(no&&!flag) flag=sz+1;
cvxs[sz++]=a;
}
k=sz;
if(flag) ok=0;
flag=0;
for(i=max(1ll,n-1);i>=1;i--){
a=cvxindx[i];
no=0;
while(sz>k){
x=(points[cvxs[sz-2]]-points[cvxs[sz-1]]).toleft(points[a]-points[cvxs[sz-1]]);
if(x==0) no=1;
if(x>=0){
sz--;
if(sz<flag) flag=0;
}else{
break;
}
}
if(no&&!flag) flag=sz+1;
cvxs[sz++]=a;
}
if(flag) ok=0;
judge=ok;
ans.resize(sz+1);
for(i=1;i<=sz;i++) ans[i]=points[cvxs[i-1]];
return sz-1;
}
int fans;
bool check(point a,int sze){
for(int i=1;i<=sze;i++){
if(a==ans[i]) return 1;
// if(((ans[i]-ans[i-1])^(a-ans[i-1]))==0){
// return 1;
// }
}
return 0;
}
ll indx[N],nowpos;
bool cmp1(ll x,ll y){
int flag1=(points[x].y<points[nowpos].y||(points[x].y==points[nowpos].y&&points[x].x<points[nowpos].x));
int flag2=(points[y].y<points[nowpos].y||(points[y].y==points[nowpos].y&&points[y].x<points[nowpos].x));
if(flag1!=flag2){
return flag1<flag2;
}else{
return (points[x]-points[nowpos]).toleft(points[y]-points[nowpos])==1;
}
}
void solve(){
fans=1;
scanf("%d",&n);
points.resize(n+1);
for(int i=1;i<=n;i++){
points[i].in();
}
int sze=convexhall(points, n, ans);
ans[0]=ans[sze];
// for(int i=1;i<=sze;i++){
// ans[i].out();
// }
for(int i=1;i<=n;i++){
if(!check(points[i],sze)){
points[i].tp=1;
}else{
points[i].tp=0;
}
}
for(int i=1,tot;i<=n;i++){
if(!points[i].tp){
continue;
}
nowpos=i;
tot=0;
for(int j=1;j<=n;j++){
if(j==i) continue;
indx[++tot]=j;
}
sort(indx+1,indx+tot+1,cmp1);
indx[0]=indx[tot];
// printf("P: ");
points[i].out();
for(int j=1;j<=tot;j++){
// printf("%d[%d] %d[%d]\n",j,points[indx[j]].tp,j-1,points[indx[j-1]].tp);
points[indx[j]].out();
points[indx[j-1]].out();
if(!points[indx[j]].tp&&!points[indx[j-1]].tp){
fans++;
}
}
// printf("\n");
}
printf("%d\n",fans);
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int T=1;
while(T--)solve();
return 0;
}
/*
7
1 4
4 0
2 3
3 1
3 5
0 0
2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3736kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
x:2 y:3 x:3 y:5 x:4 y:0 x:2 y:4 x:3 y:5 x:1 y:4 x:2 y:4 x:0 y:0 x:1 y:4 x:3 y:1 x:0 y:0 x:4 y:0 x:3 y:1 x:3 y:1 x:3 y:5 x:4 y:0 x:2 y:4 x:3 y:5 x:2 y:3 x:2 y:4 x:1 y:4 x:2 y:3 x:0 y:0 x:1 y:4 x:4 y:0 x:0 y:0 x:2 y:4 x:3 y:5 x:4 y:0 x:1 y:4 x:3 y:5 x:0 y:0 x:1 y:4 x:2 y:3 x:0 y:0 x:3 y:1 x:2 y:3 x:4 ...
result:
wrong output format Expected integer, but "x:2" found